题目链接：https://www.acwing.com/problem/content/description/306/
给出n行字符串，现在将其排版，定义一个不协调度，dp中只需要记录阶段为前i个句子已经排好版，不需要记录排了多少行。通过dp进行转移之后发现如果用朴素算法一定会超时。
经过对代价函数的计算发现其满足四边形不等式，所以可以用决策单调性以及队列进行优化。
其中队列中维护的是一个决策以及决策当前覆盖的区间，也就是在这个当前的区间中，该决策是区间中每个位置的最优决策。
代码：
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> using namespace std; typedef long long ll; typedef long double ld; const int N = 1000010; int n,l,p; ld f[N]; int s[N]; struct node{ int x,l,r;//x为决策，[l,r]表示决策x在当前是f[l~r]的最优决策 }q[N]; ld calc(int i,int j){//采用决策j计算f[i],注意可能会爆double ld ans=1,num=abs((ld)(s[i]-s[j]+i-j-1-l)); for(int i=1;i<=p;i++)ans*=num; return ans+f[j]; } int get(int i,int L,int R){//找到i所属的一段对应的决策 int ans; while(L <= R){ int mid=L+R>>1; if(q[mid].l<=i && q[mid].r>=i){ ans=mid; break; } else if(q[mid].r<i)L=mid+1; else R=mid-1; } return q[ans].x; } void insert(int i,int &L,int &R){ int w=-1; while(L <= R){ //i是比这一段中原来的决策更优的决策 if(calc(q[R].l,i)<=calc(q[R].l,q[R].x))w=q[R--].l; else{ //对r来说，i是更优的决策，但是对l来说，i不是更优的决策 if(calc(q[R].r,q[R].x)>calc(q[R].r,i)){ int l=q[R].l,r=q[R].r; while(l < r){ int mid=l+r>>1; //i更优 if(calc(mid,i) > calc(mid,q[R].x))l=mid+1; else r=mid; } q[R].r=l-1;//l是满足i是最优决策的第一个位置 w=l; } break; } } if(w!=-1){ q[++R].l=w; q[R].r=n; q[R].x=i; } } void G(){ cin>>n>>l>>p; for(int i=1;i<=n;i++){ char str[40]; scanf("%s",str); s[i]=s[i-1]+strlen(str);//前i个字符的长度 } int L=1,R=1; q[1].x=0; q[1].l=1; q[1].r=n; for(int i=1;i<=n;i++){ int j=get(i,L,R);//查找覆盖i的区间对应的决策 f[i]=calc(i,j);//使用决策j计算f[i] while(L<=R && q[L].r<=i)L++;//删除队头的无用决策 q[L].l=i+1; insert(i,L,R); //使用i决策更新对[i+1,n]的决策 } if(f[n] > 1e18)puts("Too hard to arrange") ; else cout<<(ll)f[n]<<endl; puts("--------------------"); } int main(){ int t; cin>>t; while(t--){ G(); } return 0; }
实际上可以再做一次优化，因为队首的区间就是i+1开始的，所以下一个决策直接取队头的就可了，不用get函数取得到包含i+1的区间对应的决策。
代码：
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> using namespace std; typedef long long ll; typedef long double ld; const int N = 1000010; int n,l,p; ld f[N]; int s[N]; struct node{ int x,l,r;//x为决策，[l,r]表示决策x在当前是f[l~r]的最优决策 }q[N]; ld calc(int i,int j){//采用决策j计算f[i],注意可能会爆double ld ans=1,num=abs((ld)(s[i]-s[j]+i-j-1-l)); for(int i=1;i<=p;i++)ans*=num; return ans+f[j]; } void insert(int i,int &L,int &R){ int w=-1; while(L <= R){ //i是比这一段中原来的决策更优的决策 if(calc(q[R].l,i)<=calc(q[R].l,q[R].x))w=q[R--].l; else{ //对r来说，i是更优的决策，但是对l来说，i不是更优的决策 if(calc(q[R].r,q[R].x)>calc(q[R].r,i)){ int l=q[R].l,r=q[R].r; while(l < r){ int mid=l+r>>1; //i更优 if(calc(mid,i) > calc(mid,q[R].x))l=mid+1; else r=mid; } q[R].r=l-1;//l是满足i是最优决策的第一个位置 w=l; } break; } } if(w!=-1){ q[++R].l=w; q[R].r=n; q[R].x=i; } } void G(){ cin>>n>>l>>p; for(int i=1;i<=n;i++){ char str[40]; scanf("%s",str); s[i]=s[i-1]+strlen(str);//前i个字符的长度 } int L=1,R=1; q[1].x=0; q[1].l=1; q[1].r=n; for(int i=1;i<=n;i++){ f[i]=calc(i,q[L].x);//使用决策j计算f[i] while(L<=R && q[L].r<=i)L++;//删除队头的无用决策 q[L].l=i+1; insert(i,L,R); //使用i决策更新对[i+1,n]的决策 } if(f[n] > 1e18)puts("Too hard to arrange") ; else cout<<(ll)f[n]<<endl; puts("--------------------"); } int main(){ int t; cin>>t; while(t--){ G(); } return 0; }