题目：Snakes
网址：https://www.luogu.com.cn/problem/P5424
题目描述
传说，数千年前圣帕特里克消灭了哞尔兰所有的蛇。然而，蛇们现在卷土重来了！圣帕特里克节是在每年的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
6 2
7 9 8 2 3 2
输出 #1
3
说明/提示
Bessie可以设置她的捕网开始时大小为(7)。当她抓完第一组蛇之后，她将她的捕网的大小调整为(9)，保持这个大小直到抓完第(4)组蛇，再将捕网大小调整为(3)。总浪费空间为 ((7-7)+(9-9)+(9-8)+(3-2)+(3-3)+(3-2)=3(7−7)+(9−9)+(9−8)+(3−2)+(3−3)+(3−2)=3)。
如果最开始没想DP的话，这道题我可能就束手无策。
定义状态：
- 蛇组序号，这是阶段数；
- 剩余改变次数；
- 绳套大小；
为什么将绳套大小写进去呢？？由于当前状态下绳套大小不清楚，没办法估计价值。
也就是说，如果少了这一维度，状态将难以转移。
接着，想转移：一共有两种，改大小还是不改；
如果改的话，(dp[i,j,k]=min(dp[i-1,j-1,p]|a[i-1]<=p<=n)+k-g[i])，
不改的话，直接继承，(dp[i,j,k]=min(dp[i-1,j,k])+k-g[i])；
预估时间复杂度应该过不了。
我们尝试优化一下：
按照我的经验，绳子的大小一定是其中一个蛇组的个数；
也就是说，绳套大小 (kin{g})。
我们可以假设存在一个 (k
otin{g})，使得结果最优，事实上，设当前的蛇组的个数为(t)，则必有 (t<k)；
那么，当前绳套大小取 (t) 一定不使结果更差（因为(k)肯定不会是上一位的大小）。
我们可以把蛇组离散化，决策时仅需要考虑离散化的结果即可。
时间复杂度为(o(n^4))，好像还不够好。
我们再观察到第一个转移中，我们其实不必枚举，只需要用另一个转移方程将该过程变为(T(1))即可。
具体来说，就是维护(f[i,j])代表第(i)个蛇组、还剩(j)个更改机会中所有符合题意的状态的最小值。
可以考虑初始化：(dp[0,j,k]=0,dp[1~n,j,k]=infty)；
完了吗？？没有呢。
这道题需要使用滚动数组优化空间！！！
时间复杂度：(O(n^3))；
C ++ AC代码
#include<algorithm>
#include<iostream>
#include<cstring>
#include<vector>
#include<cstdio>
#include<cmath>
using namespace std;
const int SIZE = 400 + 10, INF = 1 << 30;
vector <int> table;
int n, k, tot = 0, g[SIZE], c[SIZE], dp[SIZE][SIZE], f[SIZE];
void discrete()
{
sort(table.begin(), table.end());
tot = unique(table.begin(), table.end()) - table.begin();
return;
}
int query(int x)
{
int L = 0, R = table.size() - 1, mid;
while(L < R)
{
mid = L + R >> 1;
if(table[mid] < x) L = mid + 1;
else R = mid;
}
return R;
}
int main()
{
scanf("%d %d", &n, &k);
for(int i = 1; i <= n; ++ i)
{
scanf("%d", &g[i]);
table.push_back(g[i]);
}
discrete();
for(int i = 1; i <= n; ++ i) c[i] = query(g[i]);
memset(f, 0, sizeof(f));
memset(dp, 0, sizeof(dp));
for(int i = 1; i <= n; ++ i)
{
for(int j = k; j >= 0; -- j)
{
f[j] = INF;
for(int x = 0; x < tot; ++ x)
{
int &ans = dp[j][x];
if(c[i] > x) ans = INF;
else
{
if(!j) ans = dp[j][x] + table[x] - g[i];
else ans = min(dp[j][x], f[j - 1]) + table[x] - g[i];
f[j] = min(f[j], ans);
}
}
}
}
printf("%d
", f[k]);
return 0;
}
总结回顾
这道题实际上让我想到的另外一道题：https://www.cnblogs.com/zach20040914/p/13045850.html，总感觉这两道题惊人的相似。