题解 P4953 【[USACO02FEB] Cow Cycling 奶牛赛车】

ZZJ__ · 2018-11-09 07:52:44 · 题解

看到这玩意没有题解，我来发一波。这也是蒟蒻第一篇发的题解，写的不好见谅。

首先题目大意就是n名队员，消耗体力值x，初始体力为e，求最先到达终点的奶牛的时间是多少。

明显我们知道用动态规划，那么怎么做呢？ 首先我们可以用f[i][j][k]记录当前还有i头牛，领头的还有j点体力，其余的还有k点体力，用了多长时间。 至于处理答案，每一头牛都有他的体力值，那么f[i][j][k]，每一头牛假设都可以当领头，那么他消耗的体力就是跑的圈数是多少，所以e-d就是终点，所以只要求出f[i][j][e-d]就可以了

代码如下：请勿复制，小心粽名哦！！

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,e,d,f[110][110][110],ans=2147483647;//数组开大了不介意，因为一般我都是n个一然后补零都是两个两个补的。
int main()
{
    scanf("%d%d%d",&n,&e,&d);
    memset(f,127,sizeof(f));//一开始初始化，因为求最小值，我们弄到最大
    f[n][e][e]=0;//开始n头牛，领头的都有e体力，一共体力满的
    for(int i=n;i>=1;i--)
    {
        for(int j=e;j>=0;j--)
        {
            for(int k=e;k>=0;k--)
            {
                for(int x=1;x<=10;x++)//
                {
                    if(j-x*x>=0&&k-x>=0) f[i][j-x*x][k-x]=min(f[i][j-x*x][k-x],f[i][j][k]+1);
                    if(k-x*x>=0) f[i-1][k-x*x][k-x]=min(f[i-1][k-x*x][k-x],f[i][j][k]+1);

                    //这里考虑特殊情况。如果当前的体力本来就足，否则根本跑不了。
                }
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=e;j++) ans=min(ans,f[i][j][e-d]);//最后和之前说的一样只要求出f[i][j][终点]就行了
    }
    printf("%d",ans);
    return 0;//程序再见
}