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 */