问题描述：
一首诗包含了若干个句子，对于一些连续的短句，可以将它们用空格隔开并放在一行中，注意一行中可以放的句子数目是没有限制的。小G给每首诗定义了一个行标准长度（行的长度为一行中符号的总个数），他希望排版后每行的长度都和行标准长度相差不远。显然排版时，不应改变原有的句子顺序，并且小G不允许把一个句子分在两行或者更多的行内。在满足上面两个条件的情况下，小G对于排版中的每行定义了一个不协调度, 为这行的实际长度与行标准长度差值绝对值的P次方，而一个排版的不协调度为所有行不协调度的总和。
小G最近又作了几首诗，现在请你对这首诗进行排版，使得排版后的诗尽量协调（即不协调度尽量小）。
输入：
输入文件中的第一行为一个整数T，表示诗的数量。
接下来为T首诗，这里一首诗即为一组测试数据。每组测试数据中的第一行为三个由空格分隔的正整数N，L，P，其中：N表示这首诗句子的数目，L表示这首诗的行标准长度，P的含义见问题描述。
从第二行开始，每行为一个句子，句子由英文字母、数字、标点符号等符号组成。
输出：
于每组测试数据，若最小的不协调度不超过10^18，则第一行为一个数，表示不协调度。接下来若干行，表示你排版之后的诗。注意：在同一行的相邻两个句子之间需要用一个空格分开。
如果有多个可行解，它们的不协调度都是最小值，则输出任意一个解均可。若最小的不协调度超过10^18，则输出“Too hard to arrange”（不含引号）。每组测试数据结束后输出“——————————”、。
思路：
这是一个DP应该不难想到，DP的方程也很简单：
然后我们需要将它优化，斜率优化能过6，7两个点，但后面的就比较难了。我们可以利用四边形不等式证明出这个DP是有决策单调性的(证明与p次方有关，利用什么求导搞。。反正我不懂)。然后就可以利用决策单调性来优化DP啦。
决策单调性是指：设$p[i]$为$f[i]$的最优决策，那么对于所有$j>i$都有$p[j]>=p[i]$。我们利用这个性质，可以利用单调队列+二分，在$O(nlogn)$内完成DP。
单调队列中的元素包含3个值：$p, l, r$，表示在区间$[l, r]$中的最优决策都是$p$。首先是把$(0, 0, n)$入队，然后对于每一个i： 1. 先检查队头元素的$[l, r]$是否包含了i，如果不包含就直接出队 2. 利用队头元素的最优决策$p$来更新$f[i]$ 3. 如果决策i比队尾的决策更优，那么我们就要插入决策i。于是我们就要找出区间$[l, r]$其中的最优决策都是i，首先$r$是为n（因为要靠后面决策来更新），$l$要利用二分找到。首先要清理队尾元素，也就是队尾元素整个区间$[l, r]$的决策i都更优，那么这个就可以出队。否则就在队尾元素区间$[l, r]$内二分，找到$l$的位置将决策i入队，并且更新队尾的$r$。
然后决策单调性的优化就是这样啦，自己理解了蛮久的。。。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
| #include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#define LL long double
#define INF 1e18
#define MAXN 100005
using namespace std;
int T, n, l, p, head, tail;
LL sum[MAXN], f[MAXN];
char str[MAXN];
struct Node {int p, l, r;} q[MAXN];
LL cal(int j, int i)
{
LL num=1, x=sum[i]-sum[j]+i-j-1-l;
for(int i=1; i<=p; i++) num*=abs(x);
return f[j]+num;
}
int find(int l, int r, int j, int i)
{
while(l<=r)
{
int mid=(l+r)>>1;
if(cal(j, mid)<cal(i, mid)) l=mid+1;
else r=mid-1;
}
return l;
}
int main()
{
scanf("%d", &T);
while(T--)
{
scanf("%d%d%d", &n, &l, &p);
for(int i=1; i<=n; i++)
{
scanf("%s", str);
int len=strlen(str);
sum[i]=sum[i-1]+len;
}
head=1, tail=0;
q[++tail]=(Node){0, 0, n};
for(int i=1; i<=n; i++)
{
if(head<=tail && i>q[head].r) head++;
f[i]=cal(q[head].p, i);
if(head>tail || cal(i, n)<=cal(q[tail].p, n))
{
while(head<=tail && cal(i, q[tail].l)<=cal(q[tail].p, q[tail].l)) tail--;
if(head>tail) q[++tail]=(Node){i, i, n};
else
{
int pos=find(q[tail].l, q[tail].r, q[tail].p, i);
q[tail].r=pos-1;
q[++tail]=(Node){i, pos, n};
}
}
}
if(f[n]>INF) printf("Too hard to arrange\n");
else printf("%lld\n", (long long)f[n]);
printf("--------------------\n");
}
}
|