您的位置: 首页  >  IT文章  >  决策单调性胡扯笔记

决策单调性胡扯笔记

分类: IT文章 • 2023-11-03 08:15:44

2019 年，第一届 CSP 认证的考场上，作为选手的asuldb打开了第二题。经过一番观察，他认为这道题存在决策单调性，于是开始乱写最终发现过不了样例。

最终asuldb对该题设计出了一个暴力程序，对于一组规模为(u)的数据，该程序的运行时间极有可能是(u^2)，之后又由于asuldb写错了输出，他只获得了60pts的好成绩。

之后他得知这道题只是一个普通的单调队列优化，于是他自闭了。

于是自闭的asuldb前几天决定来学一学决策单调性，看看决策单调性到底是个什么东西

大致可以分成两种策略

一、分治

主要用于优化满足决策点单调，且同一层dp值无关的问题，即(dp_i=max_{j<i}f_j+w_{j+1,i})这类的dp，需要满足四边形不等式

四边形不等式：对于(aleq bleq cleq d)，如果满足(w_{b,c}+w_{a,d}leq w_{a,c}+w_{b,d})那么就会存在决策点单调可以使用分治的策略优化

具体的分治方法就是我们对于一个区间([l,r])我们取其中点(mid)在相应的决策点区间([x,y])找到最优的决策点(k)，那么([l,mid-1])的可能决策点区间就是([x,k])，([mid+1,y])的可能决策点区间就是([k,y])；分治这两个区间就好了，复杂度显示是(O(nlog n))的

一道经典的例题cf868f

首先来证明一下为什么会满足四边形不等式，我们找到一组(aleq bleq c)，使得(d)从(c)开始递增，对于(w_{b,c}+w_{a,d})，(d)每增加(1)产生的贡献是([b,c],[a,d-1])里和(d)相同的数的个数；这个数显然要少于([a,c],[b,d-1])里和(d)相同的个数，于是有决策单调性，我们可以使用分治的策略解决这个问题

代码

#include<bits/stdc++.h>
#define re register
#define LL long long
const int maxn=1e5+5;
inline int read() {
	char c=getchar();int x=0;while(c<'0'||c>'9')c=getchar();
	while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+c-48,c=getchar();return x;
}
int n,m,L,R,a[maxn],tax[maxn];
LL g[maxn],dp[maxn],nw;
inline void add(int c,int v) {
	nw-=1ll*tax[c]*(tax[c]-1)/2ll;
	tax[c]+=v;
	nw+=1ll*tax[c]*(tax[c]-1)/2ll;
}
inline LL calc(int l,int r) {
	while(R<r)add(a[++R],1);
	while(L>l)add(a[--L],1);
	while(R>r)add(a[R--],-1);
	while(L<l)add(a[L++],-1);
	return nw;
}
void solve(int l,int r,int x,int y) {
	if(l>r) return;
	int mid=l+r>>1;dp[mid]=1e18;int id=0;
	for(re int i=x;i<=y&&i<mid;i++) {
		LL k=g[i]+calc(i+1,mid);
		if(k<dp[mid]) dp[mid]=k,id=i;
	}
	if(l==r) return;
	solve(l,mid-1,x,id);solve(mid+1,r,id,y);
}
int main() {
	n=read(),m=read()-1;
	for(re int i=1;i<=n;i++) a[i]=read();
	L=R=1;tax[a[1]]=1;
	for(re int i=1;i<=n;i++) dp[i]=calc(1,i);
	while(m--) {
		for(re int i=1;i<=n;i++)g[i]=dp[i];
		solve(1,n,1,n);
	}
	printf("%lld
",dp[n]);
	return 0;
}

二、二分单调栈

主要用于优化(dp_i=max_{j<i}dp_j+w_{j+1,i})类的转移，是一种更为广义的斜率优化

一道例题[JSOI2011]柠檬

首先观察到我们划分出来的区间首尾肯定是同色的，而且首尾的颜色就是我们选择的颜色；如果首位不是我们所选择的颜色，我们完全可以选一个更小的区间使得贡献不变。

于是可以写出这样的方程(dp_{i}=max_{jleq i,a_j=a_i}dp_{j-1}+a_i(s_i-s_j+1)^2)，其中(s_i=sum_{j=1}^i[a_j=a_i])

我们思考一下其中的决策单调性，对于(i)这个位置，如果存在(j,k,j<k)这样的两个转移，这个时候(j)转移已经要优于(k)转移了，那么对于比(i)更大的位置，(j)转移还是要优于(k)，因为(j)的增长速度要快于(k)

于是我们可以维护一个存储决策点的栈，设(f(j,k))表示决策(j)最早在什么时候好于决策(k)，这个可以在一个(log)时间内二分求出，那么这个栈中任意三个连续元素(j,k,l)肯定会满足(f(j,k)>f(k,l))；否则(k)这个决策点就太没用了，在(k)比(l)优的时候已经有一个比(k)更优的了，这样(k)永远也不会是最优决策了，对于这样的(k)我们不应该留在栈中

于是这道题我们对于每一种颜色维护一个单调栈就好了，复杂度(O(nlog n))

#include<bits/stdc++.h>
#define re register
#define LL long long
#define lst(x) stk[x][stk[x].size()-1]
#define Lst(x) stk[x][stk[x].size()-2]
inline int read() {
	char c=getchar();int x=0;while(c<'0'||c>'9')c=getchar();
	while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+c-48,c=getchar();return x;
}
const int maxn=1e5+5;
int a[maxn],p[maxn],tax[10005],n;
LL dp[maxn];
std::vector<int> stk[10005];
inline LL trans(int x,int c) {
	return dp[x-1]+1ll*(c-p[x]+1)*(c-p[x]+1)*a[x];
}
inline int chk(int a,int b) {
    int l=p[a]>p[b]?p[a]:p[b],r=n,nw=n+1;
	while(l<=r) {
		int mid=l+r>>1;
		if(trans(a,mid)>=trans(b,mid)) r=mid-1,nw=mid;else l=mid+1;
	}
	return nw;
}
int main() {
	n=read();for(re int i=1;i<=n;i++)a[i]=read(),p[i]=++tax[a[i]];
	for(re int i=1;i<=n;i++) {
		re int c=a[i];
		while(stk[c].size()>=2&&chk(Lst(c),lst(c))<=chk(lst(c),i)) stk[c].pop_back();
                //维护单调栈的性质
		stk[c].push_back(i);
		while(stk[c].size()>=2&&chk(Lst(c),lst(c))<=p[i]) stk[c].pop_back();
                //如果栈尾在当前不是最优的，那么在以后肯定也不是，于是弹栈
		dp[i]=trans(lst(c),p[i]);
	}
	printf("%lld
",dp[n]);return 0;
}

相关推荐