NYOJ 737 石子归并问题 （区间DP1）

题目链接：见这里

题意：中文题目

解题方法：基础区间DP。要求n个石子归并，我们根据dp的思想划分成子问题，先求出每两个合并的最小代价，然后每三个的最小代价，依次知道n个。定义状态dp [ i ] [ j ]为从第i个石子到第j个石子的合并最小代价。则有：

那么我们就可以从小到大依次枚举让石子合并，直到所有的石子都合并。
复杂度: O(n * n * n)

int n, dp[maxn][maxn],a[maxn], sum[maxn];

int main()
{
    while(scanf("%d", &n) != EOF)
    {
        CLR(sum, 0);
        CLR(dp, 0);
        REP2(i, 1, n) scanf("%d", &a[i]);
        REP2(i, 1, n) sum[i] = sum[i - 1] + a[i];
        for(int len = 2; len <= n; len++){
            for(int i = 1; i + len - 1 <= n; i++){
                int j = i + len - 1;
                dp[i][j] = INF;
                for(int k = i; k < j; k++){
                    dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + sum[j] - sum[i -1]);
                }
            }
        }
        printf("%dn", dp[1][n]);
    }
    return 0;
}

这里哈有一种优化这个DP的方式，叫做平行四边形优化，记用一个s【i】【j】=k 表示区间 i—j 从k点分开才是最优的，这样的话我们就可以优化掉一层复杂度，变为O（n * n）

代码如下：

int n, s[maxn][maxn], dp[maxn][maxn],a[maxn], sum[maxn];

int main()
{
    while(scanf("%d", &n) != EOF)
    {
        CLR(sum, 0);
        CLR(dp, 0);
        REP2(i, 1, n) scanf("%d", &a[i]), s[i][i] = i;
        REP2(i, 1, n) sum[i] = sum[i - 1] + a[i];
        for(int len = 2; len <= n; len++){
            for(int i = 1; i + len - 1 <= n; i++){
                int j = i + len - 1;
                dp[i][j] = INF;
                for(int k = s[i][j - 1]; k <= s[i + 1][j]; k++){
                    if(dp[i][j] > dp[i][k] + dp[k + 1][j] + sum[j] - sum[i - 1]){
                        dp[i][j] = dp[i][k] + dp[k + 1][j] + sum[j] - sum[i - 1];
                        s[i][j] = k;
                    }
                }
            }
        }
        printf("%dn", dp[1][n]);
    }
    return 0;
}

最后

以上就是单身哈密瓜为你收集整理的NYOJ 737 石子归并问题 （区间DP1）的全部内容，希望文章能够帮你解决NYOJ 737 石子归并问题 （区间DP1）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。