poj 1964 Cow Cycling（dp）

/*
一开始想的二维的 只维护第几只牛还有圈数
后来发现每只牛的能量是跟随每个状态的
所以再加一维  f[i][j][k]表示第i只牛 领跑的j全 已经消耗了k体力
转移的话分两类
1.换一只牛领跑 那么就从f[i][j][k]转移到f[i+1][j][j] 
2.不换 那就枚举i领跑几圈l f[i][j-l][k-l*l]转移到f[i][j][k] 时间++ 
*/
#include
#include
#include
#define maxn 110
using namespace std;
int n,d,e,f[maxn][maxn][maxn],ans=0x7fffffff;
int main()
{scanf("%d%d%d",&n,&e,&d);memset(f,127/3,sizeof(f));f[1][0][0]=0;for(int i=1;i<=n;i++)for(int j=1;j<=d;j++)for(int k=1;k<=e;k++){for(int l=1;l<=d;l++)//这只领跑几圈 
              {if(jcontinue;f[i][j][k]=min(f[i][j][k],f[i][j-l][k-l*l]+1);}  f[i+1][j][j]=min(f[i+1][j][j],f[i][j][k]);//换一只牛领跑 
          }for(int i=1;i<=e;i++)ans=min(ans,f[n][d][i]);printf("%d
",ans);return 0;
}