首页 > 代码库 > POJ 2181 Jumping Cows DP
POJ 2181 Jumping Cows DP
题意:n<=2e5件物品 按照1~n顺序选择物品,每件物品可以拿或者不拿,奇数次拿物品分数+a[i],偶数次拿分数-a[i] 问最大得分?
显然每件物品有2种状态,第奇数次拿,第偶数次拿(不拿话 ans就不统计第i个)
设dp[i][1,2] 前i件物品 最后一件状态i为1,2;
dp[i][1]=max(dp[j][2])+a[i] 1<=j<=i(j~i不拿) 保持前缀i中最大的dp[j][2]即可
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <cstdio>
using namespace std;
const int N=2e5+20;
const int inf=2e8;
int n,a[N];
int dp[N][3];
int main()
{
while(cin>>n)
{
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
memset(dp,0,sizeof(dp));
int ans=0,fir=0,sec=0;
for(int i=1;i<=n;i++)
{
dp[i][1]=sec+a[i];
dp[i][2]=fir-a[i];
sec=max(sec,dp[i][2]);
fir=max(fir,dp[i][1]);
ans=max(ans,max(dp[i][1],dp[i][2]));
}
cout<<ans<<endl;
}
return 0;
}
POJ 2181 Jumping Cows DP
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。