[HYBZ 1563/NOI2009 day1 诗人小G]决策单调优化、动态规划**

题目地址：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 #include #include #include using namespace std;
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        mid=(l+r)/2;
        if (w(Q[tail].p,mid)>=w(i,mid)) r=mid;
                                   else l=mid+1;
    }
    if (w(Q[tail].p,l)    Q[++tail].p=i;
    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");
    }   
}