甲蟲

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=j,x_i=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)?(a[i+1]?a[i]),f[i+1][j][1]+(k?len+1)?(a[j]?a[i]))\\ f[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]))\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）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。