奶牛在N分钟内锻炼，在每一分钟他可以选择跑步或者休息，每跑一分钟疲劳度加1,每休息一份中疲劳度减1。休息时必须等到疲劳度为0才能继续跑，每分钟所能跑的距离为Di，在跑的过程中疲劳度不能超过m，求奶牛可以跑得最长距离；
dp的题目，拿过来果断的想不出状态转移方程啊，对dp的感觉还是这么弱，以后要加强锻炼。一共有n个点，有限制m,这不是很典型的二维dp码？
dp[i][j] 表示在i分钟时疲劳度为j所能跑得最远距离则有状态转移方程：
如果选择跑步：dp[i][j] = dp[i - 1][j - 1] + val[i] (1<= j <= m && j <= i)
如果选择休息：dp[i][0] = max(dp[i - 1][0],dp[i - j][j]) (i - j >= j) 第二种选择dp[i - j][j]是在i - j >= j时才有的情况因为只有这时前边才会出现疲劳度达到m后在休息的。。
dp好强打。。。。膜拜DP
View Code #include#include #include #define N 10007#define M 507using namespace std;int val[N];int n,m;int dp[N][M];int main(){ int i,j; scanf("%d%d",&n,&m); for (i = 1; i <= n; ++i) scanf("%d",&val[i]); memset(dp,0,sizeof(dp)); for (i = 1; i <= n; ++i) { dp[i][0] = dp[i - 1][0]; for (j = 1; j <= i && j <= m; ++j) { if (i - j >= j) dp[i][0] = max(dp[i][0],dp[i - j][j]); dp[i][j] = dp[i - 1][j - 1] + val[i]; } } printf("%d\n",dp[n][0]); return 0;}