题解：P4953 [USACO02FEB] Cow Cycling

考虑 dp。设 dp_{i,j,k} 表示要到达还剩 i 个奶牛，领头的体力剩 j，且其它牛体力剩 k 的状态，最少需要的时间。

从后往前 dp，每次枚举这一分钟要骑的圈数，然后分要不要换一个领队的情况讨论并转移即可。

具体的，这一分钟骑 c 圈时，若不换一个领队，那么 dp_{i,j-c^2,k-c}=dp_{i,j,k}+1，否则 dp_{i-1,k-c^2,k-c}=dp_{i,j,k}+1，这里要取最小值。

最后需要令 k=e-d，枚举所有的 i 和 j，然后选出最小的那个答案，因为总共骑 d 圈的话后面的奶牛剩余体力一定是 e-d。如果 i=1 或 0 也没关系，同样可以直接用 dp_{i,j,k}。

时间复杂度 O(NE^2D)，可以通过。

#include<bits/stdc++.h>
#define chmin(x,y) x=min(x,y)
using namespace std;
const int N=101;
int dp[N][N][N];
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    int n,e,d;cin>>n>>e>>d;
    if(e<d)return cout<<0,0;
    memset(dp,0x3f,sizeof dp);
    dp[n][e][e]=0;
    for(int i=n;i>=1;i--){
        for(int j=e;j>=0;j--)for(int k=e;k>=0;k--){
            for(int ci=1;ci<=d;ci++){
                if(j-ci*ci>=0&&k-ci>=0)chmin(dp[i][j-ci*ci][k-ci],dp[i][j][k]+1);
                if(k-ci*ci>=0&&k-ci>=0)chmin(dp[i-1][k-ci*ci][k-ci],dp[i][j][k]+1);
            }
        }
    }
    int ans=0x3f3f3f3f;
    for(int i=1;i<=n;i++){
        for(int j=0;j<=e;j++){
            ans=min(ans,dp[i][j][e-d]);
        }
    }
    cout<<ans;
    return 0;
}