老感覺是貪心，一直沒明白，我一直覺得貪心能做出來，區間DP做這個題，理解不了，索性，先放放，過兩天回頭再看看，剛開始從簡單題開始，先做點簡單題讓自己理解。

附上我最敬佩大佬acm_cxlove的博客http://blog.csdn.net/acm_cxlove/article/details/7854526
注意是一定程度上調整，也就是入堆棧的順序是確定的，第一反應的貪心肯定是錯的
由于受堆棧的影響，總覺得要維護堆棧的狀態，這樣就掛了 ~~~~
其實是一個區間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 long using 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; }

總結

以上是生活随笔為你收集整理的HDU 4283 You Are the One的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。