题目描述
传说，数千年前圣帕特里克消灭了哞尔兰所有的蛇。然而，蛇们现在卷土重来了！圣帕特里克节是在每年的3月17日，所以Bessie要用彻底清除哞尔兰所有的蛇来纪念圣帕特里克。
Bessie装备了一个捕网，用来捕捉 N 组排成一行的蛇（1≤N≤400）。Bessie必须按照这些组在这一行中出现的顺序捕捉每一组的所有蛇。每当Bessie抓完一组蛇之后，她就会将蛇放在笼子里，然后带着空的捕网开始捕捉下一组。
一个大小为S 的捕网意味着Bessie可以抓住任意包含 g 条的一组蛇，其中 g≤s 。然而，每当Bessie用大小为 s 的捕网抓住了一组 g 条蛇，就意味着浪费了s−g 的空间。Bessie可以任意设定捕网的初始大小，并且她可以改变 K 次捕网大小（1≤K < N ）。
请告诉Bessie她捕捉完所有组的蛇之后可以达到的总浪费空间的最小
输入输出格式
输入格式：
输入的第一行包含 N 和 K 。
第二行包含 N 个整数 a1,…,aN ，其中ai（0≤ai≤10^6）为第 i 组蛇的数量。
输出格式：
输出一个整数，为Bessie抓住所有蛇的总浪费空间的最小值
解题思路
题目想要我们做的：给你一个长度为n的序列，你可以将它分成不大于k+1段连续子序列，求每段序列的最大值乘序列长度减去序列的和的和的最小值是多少
相信大家看了我概括出来的题目大意之后应该有一点感觉了吧
再看看数据范围k<=n<=400…嗯……
于是瞬间想到一个O(n^3)的DP算法
我们先预处理一个序列的前缀和a[]，以及序列的最大值Max[][]
设f[i]表示捕捉完1~i的蛇最少浪费多少，预处理dp数组f[i]=Max[1][i]*i-a[i]
给出转移方程
while(k--)
{
for(int i=n;i>=1;--i)
for(int j=1;j<i;++j)
f[i]=min(f[i],f[j]+Max[j+1][i]*(i-j)-a[i]+a[j]);
}
来解释一下我的转移，我一共转移了k次，在执行完x(1<=x<=k)次操作后，f[i]代表的是把捕捉完1~i的蛇，期间一共换了x次捕网的最小浪费空间
中间类似一个01背包倒序降维的操作，因为换x次捕网，只能由换x-1次来转移，所以把i倒序，压掉一维
然后那个f[i]=f[j]+Max[j+1][i]*(i-j)-a[i]+a[j]就是在捕捉完1~j的蛇后将捕网大小换成Max[j+1][i]
代码
#include<cstdio>
#include<iostream>
using namespace std;
inline int read()
{
int ans=0,flag=0;
char ch=getchar();
while(ch<'0'||ch>'9'){flag|=ch=='-';ch=getchar();}
while('0'<=ch&&ch<='9'){ans=(ans<<1)+(ans<<3)+(ch^48);ch=getchar();}
return flag?-ans:ans;
}
inline int max(int x,int y){return x>y?x:y;}
int n,k,a[405];
int f[405];
int Max[405][405];
int main()
{
n=read();k=read();
for(int i=1;i<=n;++i)
{
Max[i][i]=read();
a[i]=a[i-1]+Max[i][i];
}
for(int i=1;i<=n;++i)
for(int j=i+1;j<=n;++j)
Max[i][j]=max(Max[i][j-1],a[j]-a[j-1]);
for(int i=1;i<=n;++i)f[i]=Max[1][i]*i-a[i];
while(k--)
{
for(int i=n;i>=1;--i)
for(int j=1;j<i;++j)
f[i]=min(f[i],f[j]+Max[j+1][i]*(i-j)-a[i]+a[j]);
}
printf("%d",f[n]);
return 0;
}
自认为我的代码是很好理解的 /滑稽
花开·花落--便是一生 