HDU4283

HDU4283 You Are the One

Descrption

有 个人要上台，每个人有一个愤怒属性 ，第 个人如果第 个上台则会产生 的愤怒值。

你可以用一个栈调整上场的顺序（可以随时入栈或出栈，初始顺序为按编号从小到大）。求最后总愤怒值的最小值。

。

Sol

考虑区间DP。

表示只考虑 区间内的所有人上台产生的最小愤怒值。

转移时枚举 表示 在第 个人后上台，那么 到 的人都要先行上台， 对总愤怒值贡献增加 ，转移到 。

对于第 到 个人，前面已经上了 个人，这部分人对总愤怒值贡献增加 ，转移到 。

前缀和优化即可。

时间复杂度 。

Code

#include<bits/stdc++.h>
const int M=105;
template<typename Tp=int>inline Tp read(){Tp x(0);int op(0);char ch=getchar();while(ch<'0'||ch>'9')op|=(ch==45),ch=getchar();while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();return op?-x:x;}

int f[M][M];
int n,D[M],S[M];

void solve(int kase){
    memset(f,0,sizeof(f));
    n=read();
    for(int i=1;i<=n;++i)S[i]=(D[i]=read())+S[i-1];
    for(int len=1;len<=n;++len)
        for(int l=1,r=len;f[l][r]=0x3f3f3f3f,r<=n;++l,++r)
            for(int k=l;k<=r;++k)
                f[l][r]=std::min(f[l][r],f[l+1][k]+(k-l)*D[l]+(k-l+1)*(S[r]-S[k])+f[k+1][r]);
    printf("Case #%d:%d\n",kase,f[1][n]);
}

int main(){
    for(int t=read(),i=1;i<=t;++i)solve(i);
    return 0;
}