首页 > 代码库 > 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]);}
| 13565515 | neopenx | 3661 | Accepted | 19956K | 157MS | C++ | 498B | 2014-10-25 17:26:32 |
POJ 3661 (线性DP)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。