[原创]NYOJ 737 Cake [区间DP]【动态规划】

2016-08-27 17:33:29 Tabris_ 阅读数：380

博客爬取于2020-06-14 22:43:35
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/52336164

题目链接:http://acm.nyist.edu.cn/JudgeOnline/status.php?pid=737
-------------------------------.
石子合并（一）
时间限制：1000 ms | 内存限制：65535 KB
难度：3
描述
有N堆石子排成一排，每堆石子有一定的数量。现要将N堆石子并成为一堆。合并的过程只能每次将相邻的两堆石子堆成一堆，每次合并花费的代价为这两堆石子的和，经过N-1次合并后成为一堆。求出总的代价最小值。
输入
有多组测试数据，输入到文件结束。
每组测试数据第一行有一个整数n，表示有n堆石子。
接下来的一行有n（0< n <200）个数，分别表示这n堆石子的数目，用空格隔开
输出
输出总代价的最小值，占单独的一行
样例输入
3
1 2 3
7
13 7 8 16 21 4 18
样例输出
9
239

------------------------------------.

解题思路:
题目要求必须是相邻的两堆才能合并 所以不能用优先队列处理
想到区间dp
dp[i][j] 表示i~j区间内的最小花费

每次维护区间合并的最小值 即可
但要注意 花费的问题是累加的 所以每一次区间的维护中应该加上区间内所有的和 用前缀和处理

状态转移方程是
dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]);

当然本题也可以采用平行四边形优化 跑的能跟快一点
方法是 用另外一个数组记录最有分割点 也就是枚举的K

附本题代码
--------------------------.

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
//#include <bits/stdc++.h>
# include <stdio.h>
# include <string.h>
# include <iostream>
using namespace std;
# define lalal puts("*****");

typedef long long LL;
const int MOD  = 1000000007;
const int maxn = 200010;
const int INF  = 0x1f1f1f1f;

int dp[222][222];
int a[222];
int sum[222];

int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        memset(dp,0,sizeof(dp));


        for(int i=0;i<n;i++)
            scanf("%d",&a[i]);

        sum[0]=a[0];
        for(int i=1;i<n;i++)
            sum[i]=sum[i-1]+a[i];

        for(int l=1;l<n;l++)
        {
            for(int i=0,j=l;j<n;i++,j++)
            {
                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("%d\n",dp[0][n-1]);
    }
    return 0;
}