P4953 [USACO02FEB]Cow Cycling

$Result$

$Hyperlink$

https://www.luogu.com.cn/problem/P4953

$Description$

有$n$头初始体力为$E$的奶牛，它们要跑$D$圈
每一分钟，它们可以选择一个速度$k$，并选出一头牛$x$领跑，必须满足领跑的这头牛不会再领跑期间体力耗尽
在这一分钟里，它们将跑过$k$圈，领跑这头牛的体力将减少$k^2$，其它牛的体力将减少$k$
如果体力不大于0，标明这头牛已经掉队了，后续不再考虑它
领跑这头牛不能在领跑期间掉队（但你可以更改领跑的牛，不过必须隔一分钟【每一分钟为单位选出一个新的领跑，当然也可以不变】）
问至少有一头牛到达终点时不掉队【或者恰好掉队也行，在物理上它等价于恰好不掉队】的最小时间

数据范围：$n\le 20,E\le 100,D\le 100$

$Solution$

$dp$
首先可以证明让牛尽量接替着领跑显然不会更劣，因此我们每次只关心上一次领跑的牛是哪个

由于我们需要一头牛在剩余体力为某个值的情况下，跑若干圈的最少时间
所以我们可以设$g_{i,j}$表示剩余体力为$i$，跑$j$圈的最少时间
初态显然是$g_{i,0}=0$
枚举领跑的速度$k$，显然有 g i , j = m i n { g i − k 2 , j − k + 1 } g_{i,j}=min{g_{i-k^2,j-k}+1} gi,j​=min{gi−k2,j−k​+1}

接下来要求$n$头牛跑完$D$圈的最少时间
设$f_{i,j}$表示$i$头牛跑完$j$圈的最少时间，我们只需要枚举上一次领跑的牛领跑$k$圈
初态显然是$f_{0,0}=0$
因为在这头领跑的牛领跑之前，它已经跟着其它牛【换言之被领跑了】$D-j$圈，所以它现在的体力是$E-(D-j)$
有转移 f i , j = m i n { f i − 1 , j − k + g E − ( D − j ) , k } f_{i,j}=min{f_{i-1,j-k}+g_{E-(D-j),k}} fi,j​=min{fi−1,j−k​+gE−(D−j),k​}

终态显然是$f_{n,D}$
复杂度为$O(E^{1.5}D+n{D}^2)$

$Code$

#include<cctype>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long
using namespace std;int n,E,D,g[101][101],f[11][101];
inline LL read()
{
	char c;LL d=1,f=0;
	while(c=getchar(),!isdigit(c)) if(c=='-') d=-1;f=(f<<3)+(f<<1)+c-48;
	while(c=getchar(),isdigit(c)) f=(f<<3)+(f<<1)+c-48;
	return d*f;
}
signed main()
{
	n=read();E=read();D=read();
	memset(g,0x3f,sizeof(g));
	for(register int i=0;i<=E;i++) g[i][0]=0;
	for(register int i=1;i<=E;i++)
	 for(register int j=1;j<=D;j++)
	  for(register int k=1;k*k<=i&&k<=j;k++) g[i][j]=min(g[i][j],g[i-k*k][j-k]+1);
	memset(f,0x3f,sizeof(f));
	f[0][0]=0;
	for(register int i=1;i<=n;i++)
	 for(register int j=0;j<=D;j++)
	  for(register int k=0;k<=j;k++) f[i][j]=min(f[i][j],f[i-1][j-k]+g[E-(D-j)][k]);
	printf("%d",f[n][D]);
}

最后

以上就是花痴含羞草为你收集整理的P4953 [USACO02FEB]Cow Cycling的全部内容，希望文章能够帮你解决P4953 [USACO02FEB]Cow Cycling所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。