题目链接: http://poj.org/problem?id=3661
题目大意：牛跑步。有N分钟，M疲劳值。每分钟跑的距离不同。每分钟可以选择跑步或是休息。一旦休息了必须休息到疲劳值为0。0疲劳值也可以花费1分钟去休息。最后疲劳值必须为0，问跑的最大距离。
解题思路：
怎么看都像个随便YY的DP。
用dp[i][j]表示第i分钟，疲劳值为j的最大距离。
首先考虑第i分钟休息问题：
①上次已经疲劳为0，这次又休息。dp[i][0]=dp[i-1][0].
②上次疲劳为k。dp[i][0]=max(dp[i][0],dp[i-k][k])，其中i-k>0
然后考虑第i分钟跑步问题
dp[i][j]=dp[i-1][j-1]+d[i]。
这样所有状态就推完了。
最后ans=dp[n][0]。
#include "cstdio"
#include "iostream"
using namespace std;
#define maxn 10005
int d[maxn],dp[maxn][];
int main()
{
//freopen("in.txt","r",stdin);
int n,m;
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++) scanf("%d",&d[i]);
for(int i=;i<=n;i++)
{
dp[i][]=dp[i-][];
for(int j=;j<=m&&i-j>;j++) dp[i][]=max(dp[i][],dp[i-j][j]);
for(int j=;j<=m;j++)
dp[i][j]=dp[i-][j-]+d[i];
}
printf("%d\n",dp[n][]); }
| 13565515 | neopenx | 3661 | Accepted | 19956K | 157MS | C++ | 498B | 2014-10-25 17:26:32 |