http://acm.hdu.edu.cn/showproblem.php?pid=1692

模拟题  比赛的时候居然没有看这道题  哎  还是卡死在那个一直被我们认为是dp的该死的floyed上了啊

#include<stdio.h>
int w[100001];
int l[100001];
int p[100001];
int main()
{
 int n,t,k=0,j,i,min,energy,water;
 scanf("%d",&t);
 while(t--)
 {
  k++;
  scanf("%d",&n);
  for(i=1;i<=n;i++)
   scanf("%d%d%d",&w[i],&l[i],&p[i]);
  min=p[n];
  for(i=n-1;i>0;i--)
  {
   energy=0;
   water=0;
   for(j=i;j<=n;j++)
   {
    if(water+w[j]<=l[j])
    {
     energy+=p[j];
     water+=w[j];
    }
    else
    {
     water+=w[j];
    }
    if(energy>min)break;
   }
   if(energy<min)
    min=energy;
  }
  printf("Case %d: Need to use %d mana points.\n",k,min);
 }
 return 0;
}