起因
我满怀欢喜的打开洛谷，发现洛谷 USACO 的绿色DP只剩下了这道！于是粗略扫了一眼，马上编码，炸了！好吧看错了题，事情又变得疏忽迷离……
题面
题目传送门
题目描述
传说，数千年前圣帕特里克消灭了哞尔兰所有的蛇。然而，蛇们现在卷土重来了！圣帕特里克节是在每年的3月17日，所以Bessie要用彻底清除哞尔兰所有的蛇来纪念圣帕特里克。
Bessie装备了一个捕网，用来捕捉 $ N $ 组排成一行的蛇（ $ 1 \leq N \leq 400 $ ）。Bessie 必须按照这些组在这一行中出现的顺序捕捉每一组的所有蛇。每当 Bessie 抓完一组蛇之后，她就会将蛇放在笼子里，然后带着空的捕网开始捕捉下一组。
一个大小为 $ s $ 的捕网意味着 Bessie 可以抓住任意包含 $ g $ 条的一组蛇，其中 $ g \leq s $ 。然而，每当 Bessie 用大小为 $ s $ 的捕网抓住了一组 $ g $ 条蛇，就意味着浪费了 $ s-g $ 的空间。Bessie 可以任意设定捕网的初始大小，并且她可以改变 $ K $ 次捕网大小（ $ 1 \leq K<N $ ）。
请告诉 Bessie 她捕捉完所有组的蛇之后可以达到的总浪费空间的最小值。
输入格式
输入的第一行包含 $ N $ 和 $ K $ 。
第二行包含 $ N $ 个整数 $ a_1, \ldots ,a_N $ ，其中 $ a_i $ （ $ 0 \leq a_i \leq 10^6 $ ）为第 $ i $ 组蛇的数量。
输出格式
输出一个整数，为 Bessie 抓住所有蛇的总浪费空间的最小值。
样例 #1
样例输入 #1
样例输出 #1
提示
Bessie 可以设置她的捕网开始时大小为 $7$。当她抓完第一组蛇之后，她将她的捕网的大小调整为 $9$，保持这个大小直到抓完第 $3$ 组蛇，再将捕网大小调整为 $3$。总浪费空间为 $ (7-7)+(9-9)+(9-8)+(3-2)+(3-3)+(3-2)=3 $ 。
思路
好吧估计就我看错了，我一开始以为不需要按顺序来这，然后光荣趋势。然后发现问题以后重新推就遇到了困难。去看了题解区，发现是一种叫做 分段DP 的玩意。没听过但是大概了解是下面这样的。
我们注意到他一定是用了一段一段的网然后调整，那么就把答案分成了若干个小段。为了抓住小段里所有的蛇，网肯定是刚刚好等于这个小段里的最大值不会浪费，于是每一段的价值就可以这样表示：
1
2
3
4
5
6
7
8
9
| inline void Init() {
for(int i = 1; i <= n; i++) {
int tot = 0, mx = 0;
for(int j = i; j <= n; j++) {
tot += a[j], mx = max(mx, a[j]);
sum[i][j] = mx * (j - i + 1) - tot;
}
}
}
|
然后就简单了，其实不过如此。但是这种新颖的方式让我眼前一亮，我相信一定会有算法基于这种思想拓展而到的。
然后我们就是枚举一个段数，枚举一个终结点，枚举一个端点，这就更简单了，直接上代码罢。
代码
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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
| #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int , int > pii;
typedef unsigned long long ull;
namespace FastIO
{
template<typename T> inline T read(T& x) {
x = 0;
int f = 1;
char ch;
while (!isdigit(ch = getchar())) if (ch == '-') f = -1;
while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
x *= f;
return x;
}
template<typename T, typename... Args> inline void read(T& x, Args &...x_) {
read(x);
read(x_...);
return;
}
inline ll read() {
ll x;
read(x);
return x;
}
};
using namespace FastIO;
const int N = 410;
int n, K;
int a[N];
inline void Input() {
read(n, K); K++;
for(int i = 1; i <= n; i++) {
read(a[i]);
}
}
int sum[N][N];
inline void Init() {
for(int i = 1; i <= n; i++) {
int tot = 0, mx = 0;
for(int j = i; j <= n; j++) {
tot += a[j], mx = max(mx, a[j]);
sum[i][j] = mx * (j - i + 1) - tot;
}
}
}
int dp[N][N];
inline void Work() {
Init();
for(int i = 0; i <= n; i++) {
for(int j = 0; j <= K; j++) {
dp[i][j] = 1e9;
}
}
dp[0][0] = 0;
for(int k = 1; k <= K; k++) {
for(int i = 1; i <= n; i++) {
for(int j = 0; j < i; j++) {
dp[i][k] = min(dp[i][k], dp[j][k - 1] + sum[j + 1][i]);
}
}
}
printf("%lld\n", dp[n][K]);
}
int main() {
int T = 1;
while(T--) {
Input();
Work();
}
return 0;
}
|
