题解 P4953 【[USACO02FEB]Cow Cycling】

devout · 2020-10-22 19:02:03 · 题解

一道比较好想代码也非常好写的一道dp题

因为牛都一样，所以我们可以考虑让一只牛领头，一直领到他累死。

用 f[i][j][k] 表示现在已经死了 i 只牛，现在领头的牛有 j 的体力，已经跑了 k 圈时的最快用时。

显然转移分为两种情况，一种是领头的牛继续领头，另一种是领头的牛不再领头，相当于累死了，这个时候我们就需要换一头新的牛来领头。

注意转移的方向，j 应当从大往小枚举

复杂度大概是 O(ne\sqrt ed) 这个级别的（

# include <bits/stdc++.h>

using namespace std;

# define Rep(i,a,b) for(register int i=a;i<=b;i++)
# define _Rep(i,a,b) for(register int i=a;i>=b;i--)
# define RepG(i,u) for(int i=head[u];~i;i=e[i].next)

typedef long long ll;

const int N=3e5+5;

template<typename T> void read(T &x){
   x=0;int f=1;
   char c=getchar();
   for(;!isdigit(c);c=getchar())if(c=='-')f=-1;
   for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+c-'0';
    x*=f;
}

int n,e,d;
int f[25][105][105];
int ans=INT_MAX; 

int main()
{
    memset(f,0x3f,sizeof(f));
    read(n),read(e),read(d);
    f[0][e][0]=0;
    Rep(i,0,n)
        _Rep(j,e,0)
            Rep(k,0,d){
                int q=1;
                while(q*q<=j&&k+q<=d){
                    f[i][j-q*q][k+q]=min(f[i][j-q*q][k+q],f[i][j][k]+1);
                    f[i+1][e-k-q][k+q]=min(f[i+1][e-k-q][k+q],f[i][j][k]+1);
                    q++;    
                }
            }
    Rep(i,0,n-1)
        Rep(j,0,e)
            ans=min(ans,f[i][j][d]);
    printf("%d\n",ans);
    return 0;
}