You Are the One HDU - 4283

1. 字首和
2. 注意枚舉的更新時的變化

#include<bits/stdc++.h>
 using namespace std;
 #define fst first
 #define sec second
 #define sci(num) scanf("%d",&num)
 #define scl(num) scanf("%lld",&num)
 #define mem(a,b) memset(a,b,sizeof a)
 #define cpy(a,b) memcopy(a,b,sizeof b)
 typedef long long LL;
 typedef pair<int,int> P;
 const int MAX_N = 110;
 const int MAX_M = 10000;
 LL dp[MAX_N][MAX_N];
 LL nums[MAX_N],sum[MAX_N];
 int main() {
     int T;
     sci(T);
     for (int cs = 1;cs <= T;cs++) {
         int N;
         sci(N);
         sum[0] = nums[0] = 0;
         for (int i = 1;i <= N;i++) {
             scl(nums[i]);
         }
         for (int i=  1;i <= N;i++) {
             sum[i] = sum[i - 1] + nums[i];
         }
         mem(dp,0);
 
         for (int len = 1;len < N;len++) {
             for (int i = 1;i + len <= N;i++) {
                 LL Min = 1e10;
                 for (int j = i ;j <= i + len;j++) {
                     LL num = nums[i] * (j - i) + dp[i + 1][j] + dp[j + 1][i + len]
                             + (sum[i + len] - sum[j]) * (j - i + 1);
                    Min = min(Min,num);
                 }
                 dp[i][i + len] = Min;
             }
         }
         printf("Case #%d: %lld\n",cs,dp[1][N]);
     }
     return 0;
 }