前言

我切掉這道題是命運(yùn)石之門的選擇

---

正題

題目鏈接:https://www.luogu.org/problemnew/show/P2101

---

題目大意

$n$個(gè)連在一起的高度$h_i$盒子。一個(gè)刷子只能直著刷而且得連續(xù)都得刷。求至少刷多少次。

---

解題思路

$f_{i,j}$表示前$i$個(gè)已經(jīng)刷完了，上一個(gè)高度為$j$的刷過來。首先我們要把$j$離散化了。
然后考慮$$f_{i,j}=min\{f_{i?1,k(k\ge j)},f_{i,j?1}+b_i?b_j\}$$
這樣橫著刷的就搞定了，但是還有豎著刷的所以就要加$(b[j]!=a[i])$
然后對(duì)于那個(gè)$k$用前綴合搞定。

---

$code$

#include<cstdio> #include<algorithm> #include<cstring> #define ll long long using namespace std; const ll N=5100; ll n,a[N],b[N],f[2][N],mins,m; int main() {scanf("%lld",&n);for(ll i=1;i<=n;i++){scanf("%lld",&a[i]);b[i]=a[i];}sort(b+1,b+1+n);m=unique(b+1,b+n+1)-(b+1);memset(f,0x3f,sizeof(f));f[0][0]=0;mins=2147483647;for(ll i=1;i<=n;i++){memset(f[i&1],0x3f,sizeof(f[i&1]));f[i&1][0]=f[~i&1][0];for(ll j=1;j<=m;j++){if(b[j]>a[i]) break;f[i&1][j]=min(f[~i&1][j],f[i&1][j-1]+b[j]-b[j-1]);}for(ll j=0;j<=m;j++){if(b[j]>a[i]) break;if(b[j]!=a[i]) f[i&1][j]+=1;if(i==n) mins=min(f[i&1][j],mins);}for(ll j=m-1;j>=0;j--)f[i&1][j]=min(f[i&1][j+1],f[i&1][j]);}printf("%lld",mins); }

總結(jié)

以上是生活随笔為你收集整理的P2101-命运石之门的选择【dp,离散化】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。