首页 > 代码库 > hdu 4283

hdu 4283

2024-11-10 12:16:38   204人阅读

题意：给出个A数列，问是否能用栈的规则控制这些数的进出，使得a[i]*i最小

思路：首先我们得知道，如果当前这个数字是第k个出来的，那么这个数字后面的k-1个数字肯定是（1---k-1）出来的，当然这k-1个数字也有可能打乱顺序出来

           dp[i][j]表示i到j中这些数字按照1---(j-i+1)排列组合的某一种顺序出来,

　　　那么dp[i][j]的第i位有可能是第1位，，第k位，，第j-i+1位，枚举，dp[i][j]=min(dp[i][j],a[i]*(k-1)+dp[i+1][i+k-1]  + dp[i+k][j]+ k* ( sum[k]-sum[i+k-1]).

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　a[i]为第k个出来+后k-1个数字+（最后面的一段出来得+前面已经有k个了，所以这一段的数字得加上k*数字和）

　　

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define inf 1e9;
 4 const int N=102;
 5 int dp[102][102];
 6 int a[N],sum[N];
 7 
 8 int main(){
 9     int t;
10     int kk=1;
11     scanf("%d",&t);
12     while(t--){
13         int n;
14         scanf("%d",&n);
15         memset(dp,0,sizeof(dp));
16         memset(sum,0,sizeof(sum));
17         for(int i=1;i<=n;i++) {
18             scanf("%d",&a[i]);
19             sum[i]=sum[i-1]+a[i];
20         }
21         for(int i=1;i<=n;i++){
22             for(int j=i+1;j<=n;j++) dp[i][j]=inf;
23         }
24         for(int l=1;l<n;l++){
25             for(int i=1;i<=n-l;i++){
26                 int j=i+l;
27 
28                 for(int k=1;k<=j-i+1;k++){
29                    dp[i][j]=min(dp[i][j],dp[i+1][i+1+k-1-1]+a[i]*(k-1)+dp[i+k][j]+k*(sum[j]-sum[i+k-1]));
30                 }
31                 //cout<<i<<" "<<j<<" "<<dp[i][j]<<endl;
32             }
33 
34         }
35         printf("Case #%d: ",kk++);
36         cout<<dp[1][n]<<endl;
37     }
38 }

 

hdu 4283


联系
我们