程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU 4283 You Are the One （區間DP）

HDU 4283 You Are the One （區間DP）

編輯：C++入門知識

題意：有 n 個人，每個人有一個diaosi值a[i]，如果第 i 個人排在第 k 位置，則他的憤怒值就為a[i]*（k-1）；

過程中有一個黑屋子，可以把人暫時放到黑屋子裡。

求總的憤怒值最小；

區間DP：對dp[i][j],我們考慮i到j的（j-i+1）個人，對於第i個人我們可以假設他在第k個位置，則前面就有k-1個人在他前面，j-k個人在他後面，所以dp[i][j]=min(dp[i][j],dp[i+1][k]+dp[k+1][j]+a[i]*(k-1)+(sum[j]-sum[i+k-1])*k)

#include
#include
#include
#include
#include
#include
#include
#include 
#include 
#include
#include
using namespace std;
#define INF 1e8
#define eps 1e-8
#define LL __int64
#define inf 1000000
#define N 100010 
#define M 100010
int main()
{
    int t,C=1;
    int dp[110][110];
    scanf("%d",&t);
    while(t--)
    {
        int n;
        scanf("%d",&n);
        int a[110],sum[110];
        sum[0]=0;
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            sum[i]=sum[i-1]+a[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;i>=1;i--)
        {
            for(int j=i+1;j<=n;j++)
            {
                for(int k=i;k<=j;k++)
                    dp[i][j]=min(dp[i][j],dp[i+1][k]+dp[k+1][j]+a[i]*(k-i)+(sum[j]-sum[k])*(k-i+1));
            }
        }
		/* 兩種方法都可以
		for(int p=1;p<=n;p++)
		{
			for(int i=1;i<=n-p;i++)
			{
				int j=i+p;
				for(int k=1;k<=(j-i+1);k++)
				{
					dp[i][j] = min(dp[i][j],dp[i+1][i+k-1]+dp[i+k][j] + (k-1)*a[i] + (sum[j]-sum[i+k-1])*k);
				}
			}
		}
		*/
        printf("Case #%d: %d\n",C++,dp[1][n]);
    }
    return 0;
}
/*
2
5
1
2
3
4
5

5
5
4
3
2
2 
*/