题意:
有n头牛,每头都有能量e,要跑d圈,跑得过程中每分钟跑x圈(自己选择),领头的消耗x*x的能量,其他的消耗x的能量,问跑完d圈最少需要多少时间。
思路:
最后的结果肯定是前面n-1头领跑后奶牛n撞线。dp[i][j][k]为前i-1头已领跑,现在i领跑,一共跑了j圈,第i头牛消耗了k的能量。dp[i][j][k]可以转移到下一分钟i继续领跑dp[i][j+a][k+a*a]+1或本分钟换牛dp[i+1][j][j]。
代码:
#include<iostream>
using namespace std;
int dp[32][128][128];int main()
{int n,e,d,i,j,k,a;scanf("%d%d%d",&n,&e,&d);for(i=0;i<=n;++i)for(j=0;j<=d;++j)for(k=0;k<=e;++k)dp[i][j][k]=INT_MAX;dp[1][0][0]=0;for(i=1;i<=n;++i)for(j=0;j<d;++j)for(k=0;k<=e;++k)if(dp[i][j][k]!=INT_MAX){for(a=0;a+j<=d&&k+a*a<=e;++a) dp[i][j+a][k+a*a]=min(dp[i][j+a][k+a*a],dp[i][j][k]+1);if(i<n)dp[i+1][j][j]=min(dp[i+1][j][j],dp[i][j][k]);} int ans=INT_MAX;for(i=0;i<=e;++i)ans=min(ans,dp[n][d][i]);if(ans==INT_MAX)printf("0");elseprintf("%d",ans);return 0;
}