正題

---

大意

有n株草，沒個時間單位開始時會增長不同的長度。每個時間單位可以將一株草剪成高度為0，求多少時間單位后能夠將草的總高度減低為h以下，或用遠不能。

---

解題思路

首先需要一段玄學推理：
可以等草長高些在剪。
如果有解每個草最多只需要剪一次，因為如果要剪兩次那么你可以在第一次的時候不用剪。
然后假設每一個草都要剪一次，那么肯定先剪長得慢的，因為等你剪后面的時候這個草又會飛快的長起來。

然后就可以用dp了，先按照長得速度排序。然后用f[i][j]f[i][j]表示前i株長到第j秒時的最小長度。然后假設在k秒的時候能結束那么f[i?1][j]+h[i]+grow[i]?kf[i?1][j]+h[i]+grow[i]?k表示不剪這株，f[i?1][j?1]+grow[i]?(k?j)f[i?1][j?1]+grow[i]?(k?j)表示剪掉這株草。但是我們現在不知道k所以我們要枚舉一下。動態轉移方程：

f[i][j]=min(f[i?1][j]+h[i]+grow[i]?k,f[i?1][j?1]+grow[i]?(k?j))f[i][j]=min(f[i?1][j]+h[i]+grow[i]?k,f[i?1][j?1]+grow[i]?(k?j))

---

代碼

#include<cstdio> #include<iostream> #include<algorithm> using namespace std; int n,hight,h[51],grow[51],f[51][51]; int main() {scanf("%d%d",&n,&hight);for (int i=1;i<=n;i++) scanf("%d",&h[i]);for (int i=1;i<=n;i++) scanf("%d",&grow[i]);for (int i=1;i<n;i++)for (int j=i+1;j<=n;j++)if (grow[j]<grow[i]) {swap(grow[i],grow[j]);swap(h[i],h[j]);}for (int k=0;k<=n;k++){memset(f,127/3,sizeof(f));f[0][0]=0;for (int i=1;i<=n;i++)f[i][0]=f[i-1][0]+h[i]+grow[i]*k;for (int i=1;i<=n;i++)for (int j=1;j<=k;j++)f[i][j]=min(f[i-1][j]+h[i]+grow[i]*k,f[i-1][j-1]+grow[i]*(k-j));if (f[n][k]<=hight){printf("%d",k);return 0;}}printf("-1"); }

總結

以上是生活随笔為你收集整理的【2018.4.14】模拟赛之四-ssl2394 剪草【dp】的全部內容，希望文章能夠幫你解決所遇到的問題。

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