自动搬运

查看原文

来自洛谷，原作者为

	caeious 这个家伙很鸽，什么也没留下

搬运于2025-08-24 22:05:36，当前版本为作者最后更新于2019-01-25 14:38:27，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

这里给大家提供一个二维dp的做法。
观察到必有至少一种最优解，使得每头牛领头的时间都是是一整段。可以用反证法证明如下：

又观察到牛与牛之间没有区别。所以可以用 $dp[i][j]$ 表示一头剩余体力为 $i$ 的牛一连领头 $j$ 圈最少要几分钟，枚举第一分钟速度 $k$ 可得

$$dp[i][j] = \min \{ dp[i - k^2][j-k] + 1 \mid 1 \leq k \leq j,k^2 \leq i\} $$

边界条件：$dp[0...E][0] = 0$

再用 $f[i][j]$ 表示还剩 $i$ 头牛没 AFO 体力不支，还有 $j$ 圈要骑，最少需要几分钟。枚举第一头牛领头圈数 $k$ 可得

$$f[i][j] = \min\{f[i - 1][j - k] + dp[E - (D - j)][k] \mid 0 \leq k \leq j\} $$

边界条件：$f[0][0] = 0, f[0][1...D] = \infty$

最后的答案就是 $f[n][D]$ 的值。

复杂度是 $O(E^{1.5}D + nD^2)$，本题中约为 $10^5$，可以加强数据可以轻松跑到最优解（2019 年 1 月及之前）。

Code

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <vector>
#include <utility>
#include <set>
//#define LOCAL
#define maxe 105
#define maxd 105
#define maxn 25
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
int n,E,D;
int dp[maxe][maxd],f[maxn][maxd];
int main(){
	#ifdef LOCAL
	freopen("sample.in","r",stdin);
	freopen("sample.out","w",stdout);
	#endif
	scanf("%d%d%d",&n,&E,&D);
	if(E < D){
		puts("0");
		return 0;
	}
	memset(dp,0x3f,sizeof(dp));
	for(int i=0;i<=E;i++) dp[i][0] = 0;
	for(int i=1;i<=E;i++){
		for(int j=1;j<=D;j++){
			for(int k=1;k <= j && k * k <= i;k++){
				dp[i][j] = min(dp[i][j],dp[i - k * k][j - k] + 1);
			}
		}
	}
	memset(f,0x3f,sizeof(f));
	f[0][0] = 0;
	for(int i=1;i<=n;i++){
		for(int j=0;j<=D;j++){
			int p = D - j;
			for(int k=0;k<=j;k++){
				f[i][j] = min(f[i][j],f[i - 1][j - k] + dp[E - p][k]);
			}
		}
	}
	printf("%d\n",f[n][D]);
	return 0;
}