est

【问题描述】
BG 是一个著名的诗人，经常作诗自娱自乐。但是，他一直被一件事情所困扰，那就是
诗的排版问题。
一首诗包含了若干个句子，对于一些连续的短句，可以将它们用空格隔开并放在同一行
中，注意一行中可以放的句子数目是没有限制的。 BG 给每首诗定义了一个行标准长度 M （行
的长度为一行中符号的总个数），他希望排版后每行的长度都和前一行相差不远，且不能超
过行标准长度。显然排版时，不应改变原有的句子顺序，并且 BG 不允许把一个句子分在两
行或者更多的行内。在满足上面两个条件的情况下，BG 对于排版中的每行定义了一个不协
调度，为这行的实际长度与前一行实际长度的差值绝对值（第一行为 0）。一个排版的不协
调度为所有行不协调度的总和。
TYZ 最近作了几首诗，现在他想让 BG 对作品润色。当然他希望能尽可能取悦 BG，所
以请你对这些诗进行排版，使得排版后的不协调度最小
【输入格式】
第一行两个整数 M，N。M 代表行标准长度，N 代表有 N 个句子
第二行给出 N 个数，代表着 N 个句子格子的长度。
【输出格式】
输出仅一行，表示最小不协调度
【样例输入】
6 4
4 3 2 5
【样例输出】
3
【数据范围】
30% N<=100
100% N<=2000
1<=M,sigma(Ai)<=1e9
题目保证有解

　　F[i,j]表示前j个单词，最后一行是[i,j]的最小代价。

　　F[i,j]=min{F[k,i-1]+|S[i,j]-S[k,i-1]|}

　　将绝对值拆开

　　1） s[i][j]>=s[k][i-1]，此时随着j的增加，k的取值范围不断向左移（减小）[k,i-1]　　

　　2） s[i][j]<s[k][i-1]，此时随着j的减小，k的取值范围不断向右移（增加）[1,k]

　　直接前后缀维护最大值即可。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int inf=1e9;
 4 int M,N,ans;
 5 int f[2010][2010],s[2010][2010];
 6 int a[2010];
 7 int main(){
 8     freopen("est.in","r",stdin);
 9     freopen("est.out","w",stdout);
10 
11     scanf("%d%d",&M,&N);
12     for (int i=1;i<=N;i++)
13         scanf("%d",&a[i]);
14     
15     for (int i=1;i<=N;i++)
16         for (int j=i;j<=N;j++)
17             s[i][j]=s[i][j-1]+a[j]+(j!=i);//前缀和 + 空格 
18     
19     for(int i=0;i<=2009;i++){
20         for(int j=0;j<=2009;j++)
21             f[i][j]=inf;
22     }
23     for (int i=1;i<=N;i++)
24         if (s[1][i]<=M)
25             f[1][i]=0;
26     
27     for (int i=2;i<=N;i++){
28         int k=i;
29         int Min=inf;
30         //s[i][j]>=s[k][i-1]，此时随着j的增加，k的取值范围不断向左移（增加）[k,i-1]    
31         for(int j=i;j<=N;j++){// i ~ j为当前行的诗句 
32             if (s[i][j]<=M){
33                 while (k>1&&s[k-1][i-1]<=s[i][j]){
34                     k--;
35                     Min=min(Min,f[k][i-1]-s[k][i-1]);
36                 }
37                 f[i][j]=Min+s[i][j];
38             }
39         }
40         
41         //s[i][j]<s[k][i-1]，此时随着j的减小，k的取值范围不断向右移（减小）[1,k]
42         //直接前后缀维护最大值即可。
43         k=1;Min=inf;
44         for (int j=N;j;j--){ 
45             if (s[i][j]<=M){
46                 while (k<=i&&s[i][j]<=s[k][i-1]){
47                     Min=min(Min,f[k][i-1]+s[k][i-1]);
48                     k++;
49                 }
50                 f[i][j]=min(f[i][j],Min-s[i][j]);
51             }
52         }
53     }
54     ans=inf;
55     for (int i=1;i<=N;i++)
56         ans=min(ans,f[i][N]);
57     printf("%d",ans);
58     
59     return 0;
60 }

est

推荐阅读