hdu 4283 You Are the One 区间DP-白红宇

hdu 4283 You Are the One 区间DP

阅读量：5304 次

发布时间：2019-06-14

本文共 1700 字，大约阅读时间需要 5 分钟。

题意:

给定一个长度为n的序列表示人，每个人都有一个愤怒系数与之对应。他们依次上台，当第k个人上台时，他的愤怒值为(k - 1)*Di. 给定一个小黑屋相当于栈，来调整上台顺序使总的愤怒值最小

思路：

区间DP dp[i][j]表示第i个人到第j个人区间上台愤怒值的最小值。对于区间[x][y]如果x在第i个位置上台，则有x + 1,x + 2,.....,x+i,x ,x + i + 1.....y则将整个区间分为[x+ 1][x+i]和[x+i+1][y]两个小区间这样局部最优的思想就出来了。 dp[x][y] = min(dp[x][y],DP(x + 1,x + i) + DP(x + i + 1,y) + a[x]*i + (i + 1)*(s[y] - s[x + i])); a[x]*i表示x在第i个位置上台，再加上x+i + 1到y区间的值（这里不好理解，也不好说，就是以后的枚举的0-y -x是减去(i + 1)的了。。所以要加上）

View Code

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              #include 
               
                #define CL(a,num) memset((a),(num),sizeof(a))#define iabs(x) ((x) > 0 ? (x) : -(x))#define Min(a,b) (a) > (b)? (b):(a)#define Max(a,b) (a) > (b)? (a):(b)#define ll __int64#define inf 0x7f7f7f7f#define MOD 100000007#define lc l,m,rt<<1#define rc m + 1,r,rt<<1|1#define pi acos(-1.0)#define test puts("<------------------->")#define maxn 100007#define M 100007#define N 107using namespace std;//freopen("din.txt","r",stdin);int dp[N][N];int s[N],a[N];int DP(int x,int y){ int i; if (dp[x][y] != inf) return dp[x][y]; if (x > y) return 0; for (i = 0; i <= y - x; ++i){ dp[x][y] = min(dp[x][y],DP(x + 1,x + i) + DP(x + i + 1,y) + a[x]*i + (i + 1)*(s[y] - s[x + i])); } return dp[x][y];}int main(){ int t,i,j; int n,cas = 1; scanf("%d",&t); while (t--){ scanf("%d",&n); s[0] = 0; for (i = 1; i <= n; ++i){ scanf("%d",&a[i]); s[i] = s[i - 1] + a[i]; } for (i = 0; i <= n; ++i){ for (j = 0; j <= n; ++j) dp[i][j] = inf; } printf("Case #%d: %d\n",cas++,DP(1,n)); } return 0;}

转载于:https://www.cnblogs.com/E-star/archive/2012/09/12/2681780.html

你可能感兴趣的文章