原理
因为操场是个环，将环展开到n+n的数组里，同时也把a复制一份
s求前缀和，用于在calc函数中求出从i到j堆石子的个数和
dpmax和dpmin字面意思，存在合并i到j堆后的最大值/最小值
a存输入数据
过程
it从1开始，先合并挨着的两个，求出最大值和最小值。i和j分别代表范围的位置
就像这样：
———[i——j]———–
k枚举 $i-k 和 k-j$ 的子区间
like this: [1,2,3] -> [(1,2),3] || [1,(2,3)] => max & min
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
|
#include <iostream>
#include <cstdio>
using namespace std;
int dpmax[1001][1001], dpmin[1001][1001], a[1001], n, s[1001]; //qzh not qiezihe dp: max after combining i to j
int value(int i, int j)
{
return s[j] - s[i - 1];
}
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
a[i + n] = a[i];
}
for (int i = 1; i <= n + n; i++)
{
s[i] = s[i - 1] + a[i];
} //qzh
for (int it = 1; it < n; it++)
{
for (int i = 1, j = i + it; (i <= n + n) && (j <= n + n); i++, j = i + it;)
{
dpmin[i][j] = 0x3f3f3f3f;
for (int k = 1; k <= n; k++)
{
dpmax[i][j] = max(dpmax[i][j], dpmax[i][k] + dpmax[k + 1][j]) + value(i, j);
dpmin[i][j] = min(dpmin[i][j], dpmin[i][k] + dpmin[k + 1][j]) + value(i, j);
}
}
}
int minl = 0x3f3f3f3f, maxl = 0;
for (int i = 1; i <= n; i++)
{
maxl = max(maxl, dpmax[i][i + n - 1]);
minl = min(minl, dpmin[i][i + n - 1]);
}
return 0;
}
|