非常好的一个dp题。
一开始拿到的时候想的是二分去做，但是没写出来。
其实看到这个数据范围，应该想到状压，搜索，dp。
状压 和 搜索都不行，考虑dp。
dp[i][j][k]，表示i头牛，领头的还剩j点体力，其余的还剩k点体力。
为什么要这样设置状态？因为这题里面特殊的地方就是领头的和其余的差异。
那么，我们就去枚举领头羊当前一分钟的速度。
首先：我们考虑无解的情况。
显然，我们所有牛都以1走的路程就是最远的，即E。
那么当E < D时，无解。其余必定有解。
dp状态的转移：
需要注意的是，我们这里的初始状态为dp[n][e][e] = 0。一开始都没消耗。
这也表明了我们dp的递推需要倒着来。
有两种情况：
1.不更换领头羊，那么此时领头羊消耗sp * sp，其余的消耗sp。
此时，dp[i][j - sp * sp][k - sp] = min(dp[i][j - sp * sp][k - sp],dp[i][j][k] + 1)。
因为是倒着递推，且我们枚举的是每分钟的速度。
2.更换领头羊，这种状态不是很好想。
dp[i - 1][k - sp * sp][k - sp] = min(dp[i - 1][k - sp * sp][k - sp],dp[i][j][k] + 1)
领头羊就是其余的k里面选一只 - sp * sp，其余的 - sp。
这里为什么变成了i - 1 ?
因为我们这里更换领头羊时，直接把领头羊从队伍中删去了，所以羊就少了一只。
为什么要删去呢？因为领头羊的体力并不是k，所以k - sp不适用，所以减去就可以避免这个问题。
关于答案的统计：
假设每头羊都没当领头，那么他们的消耗 = 速度，那么到终点时剩余的体力为 E - D.
所以就是dp[i][j][E - D].
#include<bits/stdc++.h> using namespace std; typedef long long LL; typedef pair<int,int> pii; const int N = 1e5 + 5; const int M = 1e3 + 5; const LL Mod = 1000000; #define pi acos(-1) #define INF 1e12 #define dbg(ax) cout << "now this num is " << ax << endl; namespace FASTIO{ inline LL read(){ LL x = 0,f = 1;char c = getchar(); while(c < '0' || c > '9'){if(c == '-') f = -1;c = getchar();} while(c >= '0' && c <= '9'){x = (x<<1)+(x<<3)+(c^48);c = getchar();} return x*f; } } using namespace FASTIO; int dp[25][105][105]; int main() { int n,e,d;n = read(),e = read(),d = read(); if(e < d){ printf("0 "); return 0; } memset(dp,0x3f3f3f,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 sp = 1;sp <= 10;++sp){ if(j - sp * sp >= 0 && k - sp >= 0) dp[i][j - sp * sp][k - sp] = min(dp[i][j - sp * sp][k - sp],dp[i][j][k] + 1);//不更换领头 if(k - sp * sp >= 0 && k - sp >= 0) dp[i - 1][k - sp * sp][k - sp] = min(dp[i - 1][k - sp * sp][k - sp],dp[i][j][k] + 1);//更换领头 } } } } LL ans = INF; for(int i = 1;i <= n;++i){ for(int j = 0;j <= e;++j){ ans = min(ans,1LL * dp[i][j][e - d]); } } printf("%lld ",ans); system("pause"); return 0; }