差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:legal_string:jxm2001:动态规划_4 [2021/04/28 17:17]
jxm2001 [类型一]
+++ 2020-2021:teams:legal_string:jxm2001:动态规划_4 [2021/07/14 19:27] (当前版本)
jxm2001
@@ 行 74: / 行 74: @@
 </code>
 </hidden>
+==== 类型二 ====
+$$
+f_{i,j}=\min_{k=1}^{j}(f_{i-1,k}+w(k,r))
+$$
+=== 性质 ===
+若 $w(l,r)$ 满足四边形不等式，记 $g(i,j)$ 为最小最优决策点，则 $g(i,j)\le g(i,j+1)$。
+考虑 $n$ 次分治法，第 $i$ 次分治法计算 $f_{i,1\sim m}$，分治过程维护最小最优决策点的上下界，时间复杂度 $O(nm\log m)$。
+<code cpp>
+int dp[MAXN][MAXM];
+void solve(int pos,int nl,int nr,int ml,int mr){
+	if(nl>nr)return;
+	int nmid=nl+nr>>1,mmid;
+	_rep(i,ml,min(mid,mr)){
+		if(dp[pos][nmid]>dp[pos-1][i]+w(i,nmid)){
+			dp[pos][nmid]=dp[pos-1][i]+w(i,nmid);
+			mmid=i;
+		}
+	}
+	solve(pos,nl,nmid-1,ml,mmid);
+	solve(pos,nmid+1,nr,mmid,mr);
+}
+</code>
+=== 通式 ===
+$$
+f_r=\min_{l=1}^{r-1}w(l,r)
+$$
+该式为类型二样例的更加一般化形式，上述解法仍然适用。
+==== 类型三 ====
+$$
+f_r=\min_{l=1}^{r-1}(f_{l}+w(l,r))
+$$
+=== 性质 ===
+若 $w(l,r)$ 满足四边形不等式，则 $f$ 具有决策单调性。记 $g(i)$ 为最小最优决策点，则 $g(i)\le g(i+1)$。
+考虑单调队列二分，维护单调队列中每个元素的决策位置 $p$ 和负责的最优决策区间 $[l,r]$。
+每次新加入一个点 $i$，如果该点对序列末尾 $n$ 的决策不如队列末尾的点，则无视该点。
+否则和队列末尾的点比较在 $l_\text{tail}$ 位置的决策，如果 $i$ 更优则删去末尾的点，不断操作直到 $i$ 不再更优。
+最后 $i$ 和队列末尾点的最优决策分界点一定位于区间 $[l_\text{tail},r_\text{tail}]$，二分查找即可。时间复杂度 $O(n\log n)$。
+=== 例题 ===
+[[https://www.luogu.com.cn/problem/P3195|洛谷p3195]]
+**题意**
+给定序列 $c$ 和常数 $L$。已知一个区间 $[l,r]$ 的权值为 $(\sum_{i=l}^r c_i+r-l-1-L)^2$。现要求将 $[1,n]$ 划分为若干连续区间，使得权值和最小。
+**题解**
+设 $\text{dp}_i$ 表示区间 $[1,i]$ 的最小答案，设 $s_n=\sum_{i=1}^n a_n$，可以得到状态转移方程
+$$
+\text{dp}_i=\min(dp_j+(s_i+i-s_j-j-L-1)^2)
+$$
+设 $w(l,r)=(s_r+r-s_l-l-L-1)^2$，不难发现 $w(l,r)$ 满足四边形不等式，直接套用即可。
+<hidden 查看代码>
+<code cpp>
+const int MAXN=5e4+5;
+LL s[MAXN],dp[MAXN],m;
+struct Seg{
+	int lef,rig,idx;
+	Seg(int lef=0,int rig=0,int idx=0):lef(lef),rig(rig),idx(idx){}
+}que[MAXN];
+LL w(int l,int r){return (s[r]+r-s[l]-l-1-m)*(s[r]+r-s[l]-l-1-m);}
+LL cal(int l,int r){return dp[l]+w(l,r);}
+int cutSeg(int lef,int rig,int idx1,int idx2){
+	int ans;
+	while(lef<=rig){
+		int mid=lef+rig>>1;
+		if(cal(idx1,mid)<cal(idx2,mid)){
+			ans=mid;
+			lef=mid+1;
+		}
+		else
+		rig=mid-1;
+	}
+	return ans;
+}
+int main()
+{
+	int n=read_int(),head=1,tail=0;
+	m=read_int();
+	_rep(i,1,n)s[i]=read_int()+s[i-1];
+	que[++tail]=Seg(1,n,0);
+	_rep(i,1,n){
+		dp[i]=cal(que[head].idx,i);
+		while(head<=tail&&que[head].rig<=i)head++;
+		que[head].lef=i+1;
+		if(i<n&&cal(i,n)<=cal(que[tail].idx,n)){
+			while(head<=tail&&cal(que[tail].idx,que[tail].lef)>=cal(i,que[tail].lef))tail--;
+			if(head<=tail){
+				int p=cutSeg(que[tail].lef,que[tail].rig,que[tail].idx,i);
+				que[tail].rig=p;
+				que[++tail]=Seg(p+1,n,i);
+			}
+			else
+			que[++tail]=Seg(i+1,n,i);
+		}
+	}
+	enter(dp[n]);
+	return 0;
+}
+</code>
+</hidden>
+==== 补充性质 ====
+  - 若 $w_1,w_2$ 均满足四边形不等式(或区间包含单调性)，$c_1,c_2\ge 0$，则 $c_1w_1+c_2w_2$ 满足四边形不等式(或区间包含单调性)
+  - 若存在 $f(x),g(x)$ 使得 $w(l,r)=f(r)-g(l)$，则函数 $w(l,r)$ 满足四边形恒等式。若 $f(x),g(x)$ 单增，则 $w(l,r)$  满足区间包含单调性。
+  - 设 $h(x)$ 是一个凸函数，若函数 $w(l,r)$ 满足四边形恒等式并且对区间包含关系具有单调性，则复合函数 $h(w(l,r))$ 也满足四边形不等式。

CVBB ACM Team

用户工具

站点工具

差别

页面工具