题目描述
奶牛们打算通过锻炼来培养自己的运动细胞，作为其中的一员，贝茜选择的运动方式是每天进行N(1 <= N <= 10,000)分钟的晨跑。在每分钟的开始，贝茜会选择下一分钟是用来跑步还是休息。
贝茜的体力限制了她跑步的距离。更具体地，如果贝茜选择在第i分钟内跑步，她可以在这一分钟内跑D_i(1 <= D_i <= 1,000)米，并且她的疲劳度会增加1。不过，无论何时贝茜的疲劳度都不能超过M(1 <= M <= 500)。如果贝茜选择休息，那么她的疲劳度就会每分钟减少1，但她必须休息到疲劳度恢复到0为止。在疲劳度为0时休息的话，疲劳度不会再变动。晨跑开始时，贝茜的疲劳度为0。
还有，在N分钟的锻炼结束时，贝茜的疲劳度也必须恢复到0，否则她将没有足够的精力来对付这一整天中剩下的事情。
请你计算一下，贝茜最多能跑多少米。
输入格式：
第1行: 2个用空格隔开的整数：N 和 M
第2..N+1行: 第i+1为1个整数：D_i
输出格式：
输出1个整数，表示在满足所有限制条件的情况下，贝茜能跑的最大距离
样例输入：
5 2
5
3
4
2
10
样例输出：
9
分析：
很明显，这是一道动态规划题。如果去掉我在题面中加粗的那句话，那么这题是很一道普通的dp：
二维数组dp[N][M]，保证了最长N分钟，而且任意时刻疲劳值不会超过M；
dp[i][j]表示第i分钟结束后，疲劳值为j的最长路程；
最后输出dp[N][0]即可保证最后疲劳值必须降为0这个条件。
转移方程同样好写：
2种可能，第i分钟跑或休息
跑：dp[i][j]=max(dp[i-1][j-1]+dis[i],dp[i][j])
休息：dp[i][j]=max(dp[i-1][j+1],dp[i][j])
不过，这道题目增加了一个条件，也就是我在题面中加粗的那句话：“但她必须休息到疲劳度恢复到0为止”。也就是说，当贝茜选择休息时，必须一直休息直到她的疲劳值清零，才可以选择跑。因此，二维数组很难满足条件，我就使用了三维数组来解决这个问题。
代码如下：
#include<iostream>
using namespace std;
int dp[10005][505][2];
//dp[i][j][k]表示第i分钟结束后，疲劳值为j的情况下的最大距离,且k=1表示第i分钟为跑，否则为休息
int mnt,pl;
int dis[10005];
int main()
{
ios::sync_with_stdio(false);
cin>>mnt>>pl;
for(int i=1;i<=mnt;i++)
{
cin>>dis[i];
}
dp[1][0][0]=0;
dp[1][1][1]=dis[1];
for(int i=2;i<=mnt;i++)
{
//由于在转移方程中有j-1和j+1出现，所以j=0和j=pl特殊处理
//j==0,可以从3个子问题转化，dp[I-1][0][0],dp[I-1][1][0],dp[I-1][1][1];
dp[i][0][0]=max(dp[i][0][0],dp[i-1][0][0]);
dp[i][0][0]=max(dp[i][0][0],max(dp[i-1][1][0],dp[i-1][1][1]));
for(int j=1;j<pl;j++)
{
//休息 无特殊情况，可能从两个子问题转化dp[i-1][j+1][0],dp[I-1][j+1][1]
dp[i][j][0]=max(dp[i][j][0],max(dp[i-1][j+1][0],dp[i-1][j+1][1]));
//跑有特殊情况，即当上一分钟为休息时，必须休息到疲劳值清零才可继续跑
//当疲劳为1时，可能第i-1分钟选择了休息，且疲劳值为0，
if(j==1)
dp[i][j][1]=max(dp[i][j][1],dp[i-1][0][0]+dis[i]);
//当疲劳大于1时，由于j-1>0，所以只可能是第i-1分钟选择跑步，第i分钟才能继续跑
else
dp[i][j][1]=max(dp[i][j][1],dp[i-1][j-1][1]+dis[i]);
}
//j==pl
dp[i][pl][1]=max(dp[i][pl][1],dp[i-1][pl-1][1]+dis[i]);
if(pl-1==0)
dp[i][pl][1]=max(dp[i][pl][1],dp[i-1][0][0]+dis[i]);
}
cout<<max(dp[mnt][0][1],dp[mnt][0][0])<<endl;
return 0;
}
网友评论