剪草

題目大意：

有n棵小草，B某看它們很不順眼，想讓他們的高度總和不大于H，它們一開始各有一個高度，然后它們各有一個固定的生長值，B某每個單位時間可以將一棵草減掉（讓他的高度變為0），但小草每個單位時間會長一次，問B某在哪個時間可以讓小草總高度不大于H，如果永遠不可能，那就輸出-1

數據范圍限制

1 ≤ N ≤ 50，0 ≤ H ≤ 1000000

0 ≤ h[i] ≤ 100000

1 ≤ grow[i] ≤ 100000

對于20%的數據， 1 ≤ N ≤ 7。

提示

解題思路：

我們可以用f[i][j]來表示前i棵草減j次的最小高度，然后先枚舉結束時間（k），再枚舉第幾棵小草（i），再枚舉當前時間（j），就得出下圖的公式，再套進去算一下就可以了

$$f[i][j]=min\{\begin{array}{cc}f[i?1][j]+a[i].g+a[i].grow?k& 不選\\ f[i?1][j?1]+a[i].grow?(k?j)& 選\end{array}$$

注釋：

不選的話就要加上他的高度，再生長k次，選的話就不加高度，但要算出接下來要生長的高度（k-j）

#include<cstdio> #include<iostream> #include<algorithm> #include<cstring> using namespace std; int ans,n,h,f[55][55]; struct rec {int grow,g; }a[55]; bool cmp(rec x,rec y) {return x.grow<y.grow; } int main() {ans=-1;scanf("%d %d",&n,&h);for (int i=1;i<=n;++i)scanf("%d",&a[i].g);//輸入for (int i=1;i<=n;++i)scanf("%d",&a[i].grow);//輸入sort(a+1,a+1+n,cmp);//按生長速度從小到大排序for (int k=0;k<=n;++k){for (int i=1;i<=n;++i)for (int j=1;j<=i;++j)f[i][j]=2147483647;//預處理for (int i=1;i<=n;++i) f[i][0]=f[i-1][0]+a[i].g+a[i].grow*k;//處值for (int i=1;i<=n;++i)for (int j=1;j<=k;++j)f[i][j]=min(f[i-1][j]+a[i].g+a[i].grow*k,f[i-1][j-1]+a[i].grow*(k-j));//狀態轉移方程if (f[n][k]<=h)//判斷是否成立{ans=k;break;}}printf("%d",ans);//輸出return 0; }

總結

以上是生活随笔為你收集整理的【DP】剪草（jzoj 1510）的全部內容，希望文章能夠幫你解決所遇到的問題。

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