51nod 1021石子归并 dp

Love The Way You Lie 2022-08-20 13:11 125阅读 0赞

N堆石子摆成一条线。现要将石子有次序地合并成一堆。规定每次只能选相邻的2堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的代价。计算将N堆石子合并成一堆的最小代价。

例如： 1 2 3 4，有不少合并方法

1 2 3 4 => 3 3 4(3) => 6 4(9) => 10(19)

1 2 3 4 => 1 5 4(5) => 1 9(14) => 10(24)

1 2 3 4 => 1 2 7(7) => 3 7(10) => 10(20)

括号里面为总代价可以看出，第一种方法的代价最低，现在给出n堆石子的数量，计算最小合并代价。

想了很久只想出一种三重循环的方法，不过题目给出的n<=100，三重也是很快就过了的。

我们用dp\[i\]\[j\]表示合并i到j之间的元素所需要的最大代价，那么很快就可以想到递推公式了。

dp\[i\]\[j\] = min(dp\[i\]\[i+1\]+dp\[i+2\]\[j\],dp\[i\]\[i+2\]\[i+3\]\[j\],...dp\[i\]\[j-2\]+dp\[j-1\]\[j\])  +  a\[i\]+...a\[j\]

其中我们可以先利用sum\[i\]来记录a\[1\]+a\[2\]+...+a\[i\]的值。

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <cmath>
    #include <algorithm>
    using namespace std;
    
    int const maxn = 105;
    int a[maxn];
    int sum[maxn];   //sum[i] = a[1]+a[2]+...+a[i];
    int dp[maxn][maxn];//dp[i][j]表示的是合并i到j之间的元素的最大代价，其中j>i
    
    int main()
    {
        int n ;
        while(scanf("%d",&n)!=EOF)
        {
            memset(sum,0,sizeof(sum));
            memset(dp,0,sizeof(dp));
            for(int i = 1 ; i <= n ; i++)
            {
                scanf("%d",&a[i]);
                sum[i]=sum[i-1]+a[i];
            }
            for(int k = 1 ; k <= n ; k++)
            {
                for(int i = 1 ; i+k <= n ; i++)
                {
                    int j = k+i ;
                    dp[i][j] = dp[i+1][j] + sum[j]-sum[i-1];
                    for(int num = i ; num < j ; num++)
                    {
                        dp[i][j] = min(dp[i][j],(dp[i][num]+dp[num+1][j]+sum[j]-sum[i-1]));
                    }
                    //cout<<dp[i][j]<<endl;
                }
            }
            printf("%d\n",dp[1][n]);
        }
        return 0;
    }