題意：給你一些井的信息，井中原有的水，當井中的水滿足一定量后會被破壞并且這些水全部流入下一個井中，用多少能量能直接破壞這個井。然后問要想破壞第n口井至少要多少能量。

解題思路：這題首先是要找到從哪口井開始破壞，因為要破壞第n口井，要么直接破壞n，要么n之前有連續的幾口井一同被破壞，如果中間出現了一個不破壞的井，那么之前的能量就浪費了。

一般的思路肯定是兩層循環就搞定，但看到這個數據量有點怕超時，結果繞了好大的彎去找一層循環的解決辦法都錯了。最后看別人的思路，還是之前的兩層循環就可以搞定了。自己被數據給嚇到了。這題網上分類為dp，其實我感覺這題dp不是很明顯。

#include<iostream> #include<cstdio> #include<cstring> using namespace std;const int maxn = 100005; const int inf = 0x7fffff; int n,w[maxn],l[maxn],p[maxn];int main() {int t,cas = 1;scanf("%d",&t);while(t--){scanf("%d",&n);for(int i = 1; i <= n; i++)scanf("%d%d%d",&w[i],&l[i],&p[i]);int ans = inf;for(int i = 1; i <= n; i++){int sum = 0, carry = 0;for(int j = i; j <= n; j++){carry += w[j];if(carry <= l[j])sum += p[j];if(sum > ans)break;}if(sum < ans) ans =sum;}printf("Case %d: Need to use %d mana points.\n",cas++,ans);}return 0; }

總結

以上是生活随笔為你收集整理的hdu 1692(枚举+剪枝)的全部內容，希望文章能夠幫你解決所遇到的問題。

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