区间dp

HDU4283 You Are the One 题意：有n个人按1,2,3…n的顺序排好，每个人都有一个unhappy值；如果第i个人第k个上台，那么他的unhappy值为（k-1)*unhappy[i]。他们上台前需要经过一个小黑屋（相当于可以决定第i个人第几个上场），求所有人上完场最少的unhappy总和是多少； 分析：区间dp；　　i，j代表从第i个人到第j个人的最优解。现在第i个人上场的k是从1~j-i+1枚举k的所有值，因为在i上场前要有k-1个人先上场，后面还有从k到j个人，他们都是在k个人以后上场的所以每个人都要多出k倍的unhappy值来所以转移方程为： dp[i+1][i+k-1]+dp[i+k][j]+k*（k人后面的人数的unhappy的总和）+i的unhappy值*（k-1）

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; const int inf=0x3f3f3f3f; int dp[110][110],sum[110]; int main() { int ncase,Z=0; scanf("%d",&ncase); while(ncase--) { memset(sum,0,sizeof(sum));//统计unhappy值的前缀和 memset(dp,0,sizeof(dp)); int n,x[110]; scanf("%d",&n); for(int i=1; i<=n; i++) { scanf("%d",&x[i]); sum[i]=sum[i-1]+x[i]; } memset(dp, 0, sizeof(dp)); for(int i=1; i<=n; i++) { for(int j=i+1; j<=n; j++) dp[i][j] = inf; } for(int i=n-1; i>=1; i--) { for(int j=i+1; j<=n; j++) { for(int k=1; k<=j-i+1; k++) { dp[i][j]=min(dp[i][j],dp[i+1][i+k-1]+x[i]*(k-1)+dp[i+k][j]+(sum[j]-sum[i+k-1])*k); } } } PRintf("Case #%d: %d\n",++Z,dp[1][n]); } }