首页 > 代码库 > hdu2713（dp）
hdu2713（dp）
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2713
题意：有N个点，每个点都有一个值x，每次进行跳跃，当跳到自己所跳的第奇数个点是+x，第偶数个点时-x。
分析：这题dp状态转移方程不难想，dp[i][0]表示偶次数跳到第i个点是达到的最大值，dp[i][1]表示奇次数跳到第i个点达到的最大值。
则有：
dp[0][i]=max(dp[0][i-1],dp[1][i-1]-x)
dp[1][i]=max(dp[0][i-1]+x,dp[1][i-1])
#include <cstdio>#include <cstring>#include <cmath>#include <iostream>#include <algorithm>#include <queue>#include <cstdlib>#include <stack>#include <vector>#include <set>#include <map>#define LL long long#define mod 1000000007#define inf 0x3f3f3f3f#define N 150010#define clr(a) (memset(a,0,sizeof(a)))using namespace std;int dp[2][N];int main(){ int n,x; while(scanf("%d",&n)>0) { memset(dp,0,sizeof(dp)); for(int i=1;i<=n;i++) { scanf("%d",&x); dp[0][i]=max(dp[1][i-1]-x,dp[0][i-1]); dp[1][i]=max(dp[1][i-1],dp[0][i-1]+x); } printf("%d\n",max(dp[0][n],dp[1][n])); }}
hdu2713（dp）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。