题解：P4953 [USACO02FEB] Cow Cycling

lraM416 · 2024-07-22 14:05:49 · 题解

借鉴了 devout 大佬。

记 dp[i][j][k] 表示当前已经有 i 头牛来领队，当前领队牛体力为 j 及已经跑 k 圈时的最短用时。显然每一时刻都有两种情况：继续领队 or 换一头牛领队。换牛领队时它的体力即为初始体力减去当前已跑圈数（因为体力一直在消耗）和每分钟消耗体力。时间复杂度显然可过。

码风是史，凑合着看。

#include<bits/stdc++.h>
using namespace std;
int n,e,d,dp[25][105][105],mi=20220517;
signed main(){
    for(int i=0;i<=20;i++)
        for(int j=0;j<=100;j++)
            for(int k=0;k<=100;k++)
                dp[i][j][k]=20220517;
    cin>>n>>e>>d;
    dp[0][e][0]=0;
    for(int i=0;i<n;i++)//共领头牛数
        for(int j=e;j>=0;j--)//领头牛体力
            for(int k=0;k<=d;k++){//已跑圈数
                int x=1;//题中x
                while(x*x<=j&&k+x<=d){//能跑 & 不超过跑道
                    dp[i][j-x*x][k+x]=min(dp[i][j-x*x][k+x],dp[i][j][k]+1);//继续领跑
                    dp[i+1][e-x-k][k+x]=min(dp[i+1][e-x-k][k+x],dp[i][j][k]+1);//换新领队
                    x++;
                }
            }
    for(int i=0;i<n;i++)
        for(int j=0;j<=e;j++)
            mi=min(mi,dp[i][j][d]);
    cout<<mi;
    return 0;
}