首页 > 代码库 > [DP]tvvj1023 奶牛的锻炼
[DP]tvvj1023 奶牛的锻炼
思考
首先鄙人在这个题目上面思考的状态方程是 dp[i][1]表示第i分钟能跑的情况下最大路程 dp[i][0]表示第i分钟不能跑情况下的最大路程。但是在思考片刻之后发现有疲劳度的限制，所以这个方程没有办法产生联系。
在思考许久无果的情况下，跑去偷偷看了一下题解。
dp方程为 dp[i][j] i分钟j疲劳度的情况下最大距离
这不难推出
我们假设他们在跑步 dp方程为 dp[i][j] = max (dp[i-1][j-1]+距离[i],dp[i][j])
在休息时有两种情况 第一是j为0的情况下继续休息 第二个是j刚刚从m减少到0 的时间 前提是i>=j
dp[i][0]=max(dp[i-1][j-i],dp[i][0])
dp[i][0]=max(dp[i-1][0],dp[i][0])
代码实现
#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>using namespace std;int n,m,x,t,ans,d[2001],f[2001][501];int main(){ cin>>n>>m; for(int i=1;i<=n;i++)cin>>d[i]; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){ f[i][j]=max(f[i-1][j-1]+d[i],f[i][j]); if(i-j>=0) f[i][0]=max(f[i-j][j],f[i][0]); f[i][0]=max(f[i-1][0],f[i][0]); } cout<<f[n][0];return 0;}
[DP]tvvj1023 奶牛的锻炼
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。