2 条题解

  • 0
    @ 2025-10-8 17:00:43
    #include<bits/stdc++.h>
    using namespace std;
    const int N=22, M=110;
    int dp[M][M]; //一头牛剩 i体力是跑 j圈最少的时间 
    int f[N][M]; //用 i头牛跑 j圈的最少时间 
    int main(){
    	int n, E, D; scanf("%d%d%d", &n, &E, &D);
    	if(E<D) {printf("0\n"); return 0;}
    	memset(dp, 0x3f, sizeof(dp));
    	for(int i=0; i<=E; i++) dp[i][0]=0;
    	for(int i=1; i<=E; i++){
    		for(int j=1; j<=D; j++){
    			for(int k=1; k<=j && k*k<=i; k++)
    				dp[i][j]=min(dp[i][j], dp[i-k*k][j-k]+1);
    		}
    	}
    	memset(f, 0x3f, sizeof(f)); f[0][0]=0;
    	for(int i=1; i<=n; i++){
    		for(int j=0; j<=D; j++){
    			for(int k=0; k<=j; k++)
    				f[i][j]=min(f[i][j], f[i-1][j-k]+dp[E-(D-j)][k]);
    		}
    	}
    	printf("%d\n", f[n][D]);
    	return 0;
    }
    
    • 0
      @ 2025-10-8 17:00:34
      #include<bits/stdc++.h>
      using namespace std;
      const int N=22, M=110;
      int dp[M][M]; //一头牛剩 i体力是跑 j圈最少的时间 
      int f[N][M]; //用 i头牛跑 j圈的最少时间 
      int main(){
      	int n, E, D; scanf("%d%d%d", &n, &E, &D);
      	if(E<D) {printf("0\n"); return 0;}
      	memset(dp, 0x3f, sizeof(dp));
      	for(int i=0; i<=E; i++) dp[i][0]=0;
      	for(int i=1; i<=E; i++){
      		for(int j=1; j<=D; j++){
      			for(int k=1; k<=j && k*k<=i; k++)
      				dp[i][j]=min(dp[i][j], dp[i-k*k][j-k]+1);
      		}
      	}
      	memset(f, 0x3f, sizeof(f)); f[0][0]=0;
      	for(int i=1; i<=n; i++){
      		for(int j=0; j<=D; j++){
      			for(int k=0; k<=j; k++)
      				f[i][j]=min(f[i][j], f[i-1][j-k]+dp[E-(D-j)][k]);
      		}
      	}
      	printf("%d\n", f[n][D]);
      	return 0;
      }
      • 1

      USACO(106)动态规划一7:奶牛自行车队P4953 [USACO02FEB] Cow Cycling

      信息

      ID
      2297
      时间
      1000ms
      内存
      128MiB
      难度
      8
      标签
      递交数
      13
      已通过
      7
      上传者