题目地址：http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1563
【算法分析】
容易得到方程f[i]=min(f[j]+|sum[j]-sum[i]+j-i-1-L|^P)
令w(j,i)=|sum[j]-sum[i]+j-i-1-L|^P
则f[i]=min(f[j]+w[j,i])
这是经典的1D/1D模式的DP方程。
首先我们来证明一个性质：
命题1：对于i 证明： 令g(x)=|x|^P 1、P为偶数，对其求导得g(x)’=P*x^(P-1)，是单调递增的。 2、P为奇数，对其求导得g(x)’=P*x^(P-1)*(x/|x|)，容易发现，同样是单调递增的。 由于导函数单调递增，而导函数的定积分又对应于g(x)的变化量。 若a 而对于我们的w函数，随着i的增加，w[j,i]的增量是相同的， 所以相当于把g(x)不断向左平移。 由于f[i]又是固定的常数，所以命题1得证。 下面再证明另外一个性质： 命题2：方程满足决策单调性。 方程满足凸四边形不等式<=>方程满足决策单调性 w[i,j]满足凸四边形不等式当且仅当： 固定j以后，将w[i,j+1]-w[i,j]表示为i的函数，该函数的导数恒<=0。 （这个结论位于《算法艺术与信息学竞赛》的152页，定理3下面） 令g(i)=w[i,j+1]-w[i,j]，即g(i)=sum[j+1]-sum[i]+1-(sum[j]-sum[i])=a[j+1]+1。 所以g(i)为常数函数，g'(i)=0。 满足条件。
所以，综上所述，命题2得证。
于是我们就可以开一个双端队列维护决策序列了。
这个序列每一个域包含3个元素，两个是表示该点造成最优决策的区间，第3个是表示这个点是哪个。
然后我们维护这个队列即可得到最优解。
维护方法：
头部：顺次下去，如果i超过区间尾就到下一个决策区间。
尾部：每次把新弄好的i试图插进去，从后面开始，如果它负责的区域都没有i好，那么就把它删掉。由于命题1，我们只需要判断开头的结点就可以了。
当然，如果它负责的区域包含的<=i的点，那么就不可能删掉它了，因为i这个点不能完全替代它。
所以最后不可能把队列的元素都删掉，然后对队尾元素进行二分，看什么时候i这个点能够超越它。（这依赖于命题1的性质）
然后修改区间就可以了。
【其它】1A
【CODE】
#include
const int N=101111;
const long long INF=(long long)(1000000000)*(long long)(1000000000);
char S[N][33];
struct Queue_Type{int l,r,p;}Q[N];
int n,P,L,head,tail;
int a[N],sum[N],fa[N],v[N];
long long f[N];
double w(int j,int i){
int x=sum[i]-sum[j]-1-L;
if (x<0) x=-x;
double ans=1;
for (int i=1;i<=P;i++) ans*=x;
ans+=f[j];
return ans;
}
long long lw(int j,int i){
int x=sum[i]-sum[j]-1-L;
if (x<0) x=-x;
long long ans=1;
for (int i=1;i<=P;i++) ans*=x;
ans+=f[j];
return ans;
}
void input(){
cin >> n >> L >> P;
sum[0]=0;
for (int i=1;i<=n;i++){
scanf("%s",S[i]+1);
a[i]=strlen(S[i]+1);
sum[i]=sum[i-1]+a[i]+1;
}
sum[n+1]=sum[n]+1;
}
void insert(int i){
if (i==n) return;
while (Q[tail].l>i && w(Q[tail].p,Q[tail].l)>=w(i,Q[tail].l)){
tail–;
Q[tail].r=n;
}
int l=i+1,r=n,mid;
if (Q[tail].l>i+1) l=Q[tail].l;
while (l
if (w(Q[tail].p,mid)>=w(i,mid)) r=mid;
else l=mid+1;
}
if (w(Q[tail].p,l)
Q[tail].l=l;
Q[tail].r=n;
Q[tail-1].r=l-1;
}
void work(){
memset(Q,0,sizeof(Q));
head=0; tail=0; Q[0].l=1; Q[0].r=n; Q[0].p=0; f[0]=0;
for (int i=1;i<=n;i++){
while (i>Q[head].r) head++;
if (w(Q[head].p,i)>INF+10 || lw(Q[head].p,i)>INF) f[i]=-1;
else{
f[i]=lw(Q[head].p,i);
fa[i]=Q[head].p;
insert(i);
}
}
}
void output(){
if (f[n]==-1){
printf("Too hard to arrangen");
return;
}
cout << f[n] << endl;
/* memset(v,0,sizeof(v));
for (int i=n;i;i=fa[i]) v[i]=1;
for (int i=1;i<=n;i++){
printf("%s",S[i]+1);
if (v[i]) printf("n");
else printf(" ");
} */
}
int main(){
freopen("poet.in","r",stdin);
freopen("poet.out","w",stdout);
int tc;
scanf("%d",&tc);
for (int i=1;i<=tc;i++){
input();
work();
output();
printf("——————–n");
}
}
