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

题意：给定一个长度为n(<=100)的数组a(0<=ai<=100)。第k次取的数花费(k-1)*ai，每次遇到一个数（数组从前到后，栈从顶部到底部），你可以直接使用，或者如果没在栈中就将其放入栈中（先入先出，一会来取），在栈中就取它。（建议到传送门自己看看题意emm，叙述的不太行）

题解：dp[i][j]表示第0到j-i+1次取完a[i~j]中的数的最小值。我们更新dp[i][j]：

• 依据：a[i]是0~j-i+1中的第多少次取的。
• 如果为第k次取，那么
• 其中a[i]*(k-i)表示是第k-i+1次取的a[i]，那么a[i+1~k]一定是在0~k-(i+1)+1次取完的，a[k+1~j]一定是在第(k-i+1)+(0~j-(k+1)+1)次取完的（所以整体加上即可）。

代码：

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #define dbg(x) cout << #x << "===" << x << endlusing namespace std;const int N = 1e2 + 10;const int INF = 1e9;int n, a[N], sum[N];int dp[N][N];signed main() {    int T;    cin >> T;    for (int _ = 1; _ <= T; _++) {        cin >> n;        // dbg(n);        int i, j, k, len;        for (i = 1; i <= n; i++)            for (j = i + 1; j <= n; j++) dp[i][j] = INF;        for (i = 1; i <= n; i++)            scanf("%d", &a[i]), dp[i][i] = 0, sum[i] = sum[i - 1] + a[i];        for (len = 2; len <= n; len++) {            for (i = 1; i + len - 1 <= n; i++) {                j = i + len - 1;                //枚举i~j区间中i是第几次(k-i+1)取的                for (k = i; k <= j; k++) {                    dp[i][j] = min(                        dp[i][j], a[i] * (k - i) + dp[i + 1][k] + dp[k + 1][j] +                                      (sum[j] - sum[k]) * (k - i + 1));                }            }        }        printf("Case #%d: %d\n", _, dp[1][n]);    }    return 0;}
       
      
     
    
   

转载地址：https://blog.csdn.net/I_have_a_world/article/details/117672245 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！