题意：有n口井，编号为1到n，打破第i口井需要p[i]的能量，但是只要井被打破里面的水会流到下一口井，只要一口井的井水w[i]多余一个上限l[i]会自动打破，求打破第n口井需要的最少的能量
分析：hdu 把它归为dp,想了一会发现找不到最优子结构，然后看题解——根本不是dp，只是一个剪枝的题。或许有dp的解法，如果哪位大神知道还请指教。解题思路一旦局限在一个框框内很危险啊
代码：
#include<iostream>
using namespace std;
int t,n,ans,w[100005],l[100005],p[100005];
int min(int i,int j)
{
return i<j?i:j;
}
void f()
{
int tmp=p[n];
ans=p[n];
for(int i=1;i<n;i++){
int sum=p[i];
int wi=w[i];
for(int j=i+1;j<=n;j++){
wi+=w[j];
if(wi<=l[j]) sum+=p[j];
if(sum>=ans) break;
}
ans=min(ans,sum);
}
}
int main()
{
cin>>t;
for(int cas=1;cas<=t;cas++){
cin>>n;
for(int i=1;i<=n;i++) cin>>w[i]>>l[i]>>p[i];
f();
cout<<"Case "<<cas<<": Need to use "<<ans<<" mana points."<<endl;
}
}HDU 1692 Destroy the Well of Life-卡时间-（枚举+剪枝）
原文：http://blog.csdn.net/ac_0_summer/article/details/46637711