USACO 2002 Feb CowCycling

定义dp[i][j][k]为还剩i头牛,跑了j圈,第k分钟,此时领头牛的最大电力,然后用刷表法

dp[i][j][k]可以去转移dp[i][j+l][k+1],dp[i-1][j+l][k+1](l<=sqrt(dp[i][j][k])

然后当j+l>=s时,输出i+1就行了

#include<cstdio>
#include<cstring>
int dp[25][105][105];
void check(int &x,int y){
    if(x<y)x=y;
}
int main(){
    memset(dp,-1,sizeof(dp));
    int n,m,s;
    scanf("%d %d %d",&n,&m,&s);
    dp[n][0][0]=m;
    for(int i=0;i<s;i++)
        for(int j=1;j<=n;j++)
            for(int k=0;k<=s;k++)
                if(dp[j][k][i]!=-1)
                    for(int l=1;l*l<=dp[j][k][i];l++){
                        if(k+l>=s){
                            printf("%dn",i+1);
                            return 0;
                        }
                        check(dp[j][k+l][i+1],dp[j][k][i]-l*l);
                        check(dp[j-1][k+l][i+1],m-k-l);
                    }
}

最后

以上就是阔达月光为你收集整理的USACO 2002 Feb CowCycling的全部内容，希望文章能够帮你解决USACO 2002 Feb CowCycling所遇到的程序开发问题。

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