HDU 4283 You Are the One(12年天津 区间DP)
转载请注明出处，谢谢http://blog.csdn.net/acm_cxlove/article/details/7854526 by---cxlove
题目：有一个队列，每个人有一个愤怒值D，如果他是第K个上场，不开心指数就为(K-1)*D。但是边上有一个小黑屋（其实就是个堆栈），可以一定程度上调整上场程序
http://acm.hdu.edu.cn/showproblem.php?pid=4283
题目表示就看了好久，不能理解~~~Q_Q
注意是一定程度上调整，也就是入堆栈的顺序是确定的，第一反应的贪心肯定是错的
由于受堆栈的影响，总觉得要维护堆栈的状态，这样就挂了~~~~
其实是一个区间DP，dp[i][j]表示从第i个人到第j个人这段区间的最小花费（是只考虑这j-i+1个人，不需要考虑前面有多少人）
那么对于dp[i][j]的第i个人，就有可能第1个上场，也可以第j-i+1个上场。考虑第K个上场
即在i+1之后的K-1个人是率先上场的，那么就出现了一个子问题 dp[i+1][i+1+k-1-1]表示在第i个人之前上场的
对于第i个人，由于是第k个上场的，那么愤怒值便是val[i]*(k-1)
其余的人是排在第k+1个之后出场的，也就是一个子问题dp[i+k][j]，对于这个区间的人，由于排在第k+1个之后，所以整体愤怒值要加上k*(sigma(i+k--j))

#include<iostream>#include<cstdio>#include<map>#include<cstring>#include<cmath>#include<vector>#include<algorithm>#include<set>#define inf 1<<27#define N 105#define Min(a,b) ((a)<(b)?(a):(b))#define Max(a,b) ((a)>(b)?(a):(b))#define pb(a) push_back(a)#define LL long longusing namespace std;int dp[105][105];int val[105],sum[105];int main(){int n,t,cas=0;scanf("%d",&t);while(t--){scanf("%d",&n);sum[0]=0;for(int i=1;i<=n;i++){scanf("%d",&val[i]);sum[i]=sum[i-1]+val[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 l=1;l<=n-1;l++){for(int i=1;i<=n-l;i++){int j=i+l;//dp[i][j]=min(dp[i][j],dp[i+1][j]+sum[j]-sum[i]);for(int k=i;k<=j;k++)dp[i][j]=min(dp[i][j],val[i]*(k-i)+(k-i+1)*(sum[j]-sum[k])+dp[i+1][k]+dp[k+1][j]);}}printf("Case #%d: %d\n",++cas,dp[1][n]);}return 0;}

1楼yihuikang昨天 23:00

我也写了一遍，之前有些弯死活转不过来~

Re: ACM_cxlove昨天 23:09

回复yihuikangn感觉死活受堆栈的影响，总感觉一定要记录堆栈里的状态~~~