hdu4283

链接:hdu4283

题解

  • 菜鸡的我一开始甚至在想是不是模拟搜索/px
  • DP[i][j]表示区间i~j取得的最小答案,那么枚举区间i~j内第i个人上台的次序就可以划分为dp[i+1][k],dp[k+1][j]两个问题
  • 显然i点的ds值是c[i](k-i) 而i+1~j的ds值为(sum[j]-sum[i])(k-i+1)
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    #include<iostream>
    #include<cstdio>
    #include<cmath>
    #include<cstdlib>
    #include<cstring>
    #include<algorithm>
    #define rep(i,x,y) for(register int i=x;i<=y;++i)
    #define repd(i,x,y) for(register int i=x;i>=y;--i)
    #define ll long long
    using namespace std;
    const int N=107;
    const int inf=0x3f3f3f3f;
    int dp[N][N],c[N],sum[N],n,T;
    int main(){
    scanf("%d",&T);
    rep(cnt,1,T){
    scanf("%d",&n);
    rep(i,1,n){scanf("%d",&c[i]);sum[i]=sum[i-1]+c[i];}
    rep(l,2,n)rep(i,1,n-l+1){
    int j=i+l-1;
    dp[i][j]=inf;
    rep(k,i,j)dp[i][j]=min(dp[i][j],dp[i+1][k]+dp[k+1][j]+c[i]*(k-i)+(k-i+1)*(sum[j]-sum[k]));
    }
    printf("Case #%d: %d\n",cnt,dp[1][n]);
    }
    return 0;
    }