首页 > 代码库 > POJ 3661 (线性DP)

POJ 3661 (线性DP)

题目链接: 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 10005int d[maxn],dp[maxn][505];int main(){    //freopen("in.txt","r",stdin);    int n,m;    scanf("%d%d",&n,&m);    for(int i=1;i<=n;i++) scanf("%d",&d[i]);    for(int i=1;i<=n;i++)    {        dp[i][0]=dp[i-1][0];        for(int j=1;j<=m&&i-j>0;j++) dp[i][0]=max(dp[i][0],dp[i-j][j]);        for(int j=1;j<=m;j++)            dp[i][j]=dp[i-1][j-1]+d[i];    }    printf("%d\n",dp[n][0]);}
13565515neopenx3661Accepted19956K157MSC++498B2014-10-25 17:26:32

POJ 3661 (线性DP)