写在前边

区间dp的简介：区间dp总的来说可以算作是线性dp中的一种，通过由比它更小的几个区间所代表的状态转移而来，因此，区间dp的策略也主要是划分区间的方法。我们可以通过求不同区间的最值进而求得整体宏观的区间最值。

经典例题

合并石子（简单版）

Describtion

1 有N堆石子排成一排(n<=100),现要将石子有次序地合并成一堆，规定每次只能选相邻的两堆合并成一堆，并将新的一堆的石子数，记为改次合并的得分，编一程序，由文件读入堆数n及每堆石子数(<=200)；
2 
3 （1）选择一种合并石子的方案，使得做n-1次合并，得分的总和最少
4 
5 （2）选择一种合并石子的方案，使得做n-1次合并，得分的总和最多

 

Analyze

通过读题，我们可以分析，在[l,r] 区间合并之前，一定有l ~ r之间每一堆石子已经被合并，其重量是l~r之间所有石子重量的总和，所以我们可以像Floyd算法那样，在过程量中设一个参数k，k是用来标记过程中的合并的中间量，及有[l~k]和[k + 1 ~ r]一定可以合并成[l ~ r]的区间，k可以叫做转移的决策。

我们设区间长度为len，len可以表示为len = r - l + 1,通过左右端点状态表示dp的状态，我们可以写出此时的状态转移方程F[l,r] = min(max){F[l,k] + F[k + 1,r]} 我们目标求出的是F[1,N].

 1 //函数
 2 memset(f,0x3f,sizeof(f));
 3 for(int i = 1;i <= n;i++)
 4 {
 5     f[i][i] = 0;
 6     sum[i] = sum[i - 1] + a[i];
 7 }
 8 for(int len = 2;len <= n;len++)
 9 {
10     for(int l = 1;l <= n - len + 1;l++)
11     {
12         int r = l + len + 1;
13         for(int k = 1;k < r;k++)
14         {
15             f[l][r] = min(f[l][r],f[l][k] + f[k + 1][r]);
16         }
17         f[l][r] += sum[r] - sum[l - 1];
18     }
19 }

 

完整代码

 1 #include<algorithm>
 2 #include<iostream>
 3 #include<iomanip>
 4 #include<cstdio>
 5 #include<string.h>
 6 #include<cmath>
 7 #define maxn 101
 8 
 9 using namespace std;
10 
11 int f_1[maxn][maxn];
12 int sum[maxn];
13 int a[maxn];
14 int f_2[maxn][maxn];
15 int k[maxn];
16 
17 int main()
18 {
19     int n;
20     cin >> n;
21     memset(f_1, 0x3f, sizeof(f_1));
22     for (int i = 1; i <= n; i++)
23     {
24         cin >> a[i];
25     }
26     for (int i = 1; i <= n; i++)
27     {
28         f_1[i][i] = 0;
29         sum[i] = sum[i - 1] + a[i];
30     }
31     for (int j = 1; j <= n; j++)
32     {
33         f_2[j][j] = 0;
34         k[j] = k[j - 1] + a[j];
35     }
36     for (int i = 2; i <= n; i++)
37     {
38         for (int j = 1; j <= n - i + 1; j++)
39         {
40             int r = j + i - 1;
41             for (int k = j; k < r; k++)
42             {
43                 f_1[j][r] = min(f_1[j][r], f_1[j][k] + f_1[k + 1][r]);
44                 f_2[j][r] = max(f_2[j][r], f_2[j][k] + f_2[k + 1][r]);
45             }
46             f_1[j][r] += sum[r] - sum[j - 1];
47             f_2[j][r] += k[r] - k[j - 1];
48         }
49     }
50     int ans = 99999999999999;
51     int ans1 = 0;
52     ans = f_1[1][n];
53     ans1 = f_2[1][n];
54     printf("%d\n", ans);
55     printf("%d", ans1);
56     return 0;
57 }

点开以查看

 

---

the end.