题解 P1912 【[NOI2009]诗人小G】

没拿到一血很不开心，那就拿个题解的一血吧 首先这个题朴素的dp不难，dp[i] 表示 前i个句子组成的文章组成的不协调值的最小值，w[i]是句子长度的前缀和(每个句子加上一个空格)，转移是： dp[i] = dp[j]+abs(w[j]-w[i-1]-l-1)^n; 考虑如何优化 可以发现，这个转移具有决策单调性(打表或者瞪眼法) 什么是决策单调性（大家可以百度：浅析1D1D动态规划的优化） 一开始对于1-n状态最优决策是 000000000000000000000000 加入1状态以后，最优决策可能就变成了 000001111111111111111111 然后加入2 000001111111112222222222 所以我们可以维护一个单调队列，每个点记录的是该状态（0,1,2）是最优决策的区间，每次加数的时候，先判断与该状态的左端点哪个更优，如果该状态更有，就pop掉（把队列里的该点全部抛弃），否则在该点对应的区间里二分查找分界点，把位于分界点右边的换成新的决策。 本题要输出方案，用一个g[i]记录转移到该状态的决策 这样就ok了 注意： 1、本题数据要小于1e18，我们应该用long double我们不能if f[i]>1e18 then f[i]=1e18,原因是(1)中间的可能会超过1e18，而结果不一定会(2)比较决策哪个优时，同时都是1e18，无法比较哪个更优，其实如果都用long double是能比较出来的 2、输出方案时每一长句话之后不要加空格，否则会错。 附上丑陋的代码 ```cpp #include<cstdio> #include<cstring> #include<iostream> #include<vector> #include<algorithm> #include<cmath> using namespace std; long double f[101010]; int g[101010],nxt[101010],q[101010],w[101010]; int p,l; char a[101010][35]; struct Node { int l,r; }pp[101010]; long double ksm(int w,int x) { long double ans=1; int i; for(i=1;i<=x;i++) ans*=w; return ans; } long double jisuan(int x,int i) { long double ans; ans=f[x]+ksm(abs(w[i]-w[x]-1-l),p); return ans; } int main() { int T,h,t,i,tmp,len,n,right,left,mid; scanf("%d",&T); while(T--) { memset(f,0,sizeof(f)); memset(g,0,sizeof(g)); memset(nxt,0,sizeof(nxt)); memset(a,0,sizeof(a)); memset(w,0,sizeof(w)); memset(q,0,sizeof(q)); memset(pp,0,sizeof(pp)); scanf("%d%d%d",&n,&l,&p); w[0]=0; for(i=1;i<=n;i++) { scanf("%s",a[i]+1); len=strlen(a[i]+1); w[i]=w[i-1]+len+1; } h=0,t=1,q[h]=0; pp[0].l=1,pp[0].r=n; for(i=1;i<=n;i++) { while(h<t-1&&i>pp[q[h]].r)//队首比较 h++; f[i]=f[q[h]]+ksm(abs(w[i]-w[q[h]]-1-l),p); pp[q[h]].l++; g[i]=q[h]; while(h<t-1&&jisuan(q[t-1],pp[q[t-1]].l)>jisuan(i,pp[q[t-1]].l))//队尾比较 { t--; pp[q[t]].l=0; pp[q[t]].r=0; q[t]=0; } left=pp[q[t-1]].l,right=pp[q[t-1]].r;//二分查找 while(left<=right) { mid=(left+right)/2; if(jisuan(i,mid)<=jisuan(q[t-1],mid)) right=mid-1; else left=mid+1; } if(left<=n) { pp[q[t-1]].r=left-1; q[t++]=i; pp[i].l=left; pp[i].r=n; } } if(f[n]>1000000000000000000) printf("Too hard to arrange\n"); else { printf("%lld\n",(long long)f[n]); tmp=n; while(tmp!=0) { nxt[g[tmp]]=tmp; tmp=g[tmp]; } while(tmp!=n) { for(i=tmp+1;i<=nxt[tmp];i++) { printf("%s",a[i]+1); if(i!=nxt[tmp]) printf(" "); } printf("\n"); tmp=nxt[tmp]; } } printf("--------------------\n"); } return 0; } ```