甲虫

luogu 4870

题目大意：

在一个坐标轴上有n个露珠，每个露珠有m个水分，露珠会每隔一个时间单位就消失一点水分，现在有一只甲虫从原点出发，甲虫的移动速度是一个单位时间移动一个单位的距离，甲虫没碰到一个露珠就可以“秒杀”它，问甲虫最多可以迟到多少水分

前言：

本题是本蒟蒻AC的第一道紫题(＾▽＾)

输入样例

3 15 6 -3 1

输出样例

25

数据范围

$0\le n\le 300,1\le m\le 1,000,000,-10,000\le x_1,x_2,\dots ,x_n\le 10,000$
对于所有 $i\ne j,x_i\ne x_j。$

解题思路：

我们可以求最小散失水分，以此来算出最大水分
首先设$f[i][j][0/1]$为吃掉第$i$到第$j$个水分的最小散失，然后我们可以得出一下状态转移方程：
$$\{\begin{array}{c}f[i][j][0]=min(f[i+1][j][0]+(k-len+1)\ast (a[i+1]-a[i]),f[i+1][j][1]+(k-len+1)\ast (a[j]-a[i]))\\ f[i][j][1]=min(f[i][j-1][1]+(k-len+1)\ast (a[j]-a[j-1]),f[i][j-1][0]+(k-len+1)\ast (a[j]-a[i]))\end{array}$$
其中k代表要吃多少个水滴，len表示已经吃了多少个水滴，然后它表示的就是从左边和右边分别往两个方向走

代码：

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; int n,o,m,ans,a[350],f[350][350][2]; int main() {scanf("%d %d",&n,&m);for (int i=1;i<=n;++i)scanf("%d",&a[i]);a[++n]=0;//从0出发sort(a+1,a+1+n);for (int i=1;i<=n;++i)if (a[i]==0) //找到0的位置{o=i;break;}for (int k=1;k<=n;++k){memset(f,127/3,sizeof(f));f[o][o][0]=0;//初值f[o][o][1]=0;for (int len=2;len<=k;++len)for (int i=1;i<=n-len+1;++i){int j=i+len-1;f[i][j][0]=min(f[i+1][j][0]+(k-len+1)*(a[i+1]-a[i]),f[i+1][j][1]+(k-len+1)*(a[j]-a[i]));//状态转移，k-len+1f[i][j][1]=min(f[i][j-1][1]+(k-len+1)*(a[j]-a[j-1]),f[i][j-1][0]+(k-len+1)*(a[j]-a[i]));ans=max(ans,(len-1)*m-min(f[i][j][1],f[i][j][0]));//取最优答案}}printf("%d",ans); }

总结

以上是生活随笔为你收集整理的【区间DP】甲虫（luogu 4870）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。