Codeforces 358D Dima and Hares：dp【只考虑相邻元素】

题目链接：http://codeforces.com/problemset/problem/358/D

题意：

　　有n个物品A[i]摆成一排，你要按照某一个顺序将它们全部取走。

　　其中，取走A[i]的收益为：

　　　　（1）若A[i-1]和A[i+1]都没被取走，则收益为a[i]

　　　　（2）若A[i-1]和A[i+1]被取走了一个，则收益为b[i]

　　　　（3）若A[i-1]和A[i+1]都被取走，则收益为c[i]

　　　　注：将A[1]的左边和A[n]的右边视为永远有一个取不走的物品。

　　问你最大收益是多少。

题解：

　　表示状态：

　　　　dp[i][0/1] = max wealth

　　　　表示A[i]比A[i-1]先取(0)或后取(1)，此时取走A[1 to i-1]的最大收益。

　　找出答案：

　　　　ans = dp[n+1][1]

　　　　因为可以看做A[n]右边有一个不取走的物品

　　　　所以dp[n+1][1]对应的就是将所有物品取走的最大获益

　　如何转移：

　　　　dp[i][0] = max(dp[i-1][0]+b[i-1], dp[i-1][1]+c[i-1])

　　　　dp[i][1] = max(dp[i-1][0]+a[i-1], dp[i-1][1]+b[i-1])

　　　　根据A[i-1]的左右情况，加上对应的取走A[i-1]的获利，即为当前的总获利。

　　边界条件：

　　　　dp[1][0] = 0

　　　　dp[1][1] = -INF

　　　　因为将A[1]左边看作有一个物体，所以只能是A[1]先选，当前总获利为0。

AC Code:

 #include <iostream>

 #include <stdio.h>

 #include <string.h>

 #define MAX_N 3005

 #define INF 1000000000

 using namespace std;

 int n;

 int a[MAX_N];

 int b[MAX_N];

 int c[MAX_N];

 int dp[MAX_N][];

 void read()

 {

     cin>>n;

     for(int i=;i<=n;i++) cin>>a[i];

     for(int i=;i<=n;i++) cin>>b[i];

     for(int i=;i<=n;i++) cin>>c[i];

 }

 void work()

 {

     dp[][]=;

     dp[][]=-INF;

     for(int i=;i<=n+;i++)

     {

         dp[i][]=max(dp[i-][]+b[i-],dp[i-][]+c[i-]);

         dp[i][]=max(dp[i-][]+a[i-],dp[i-][]+b[i-]);

     }

     cout<<dp[n+][]<<endl;

 }

 int main()

 {

     read();

     work();

 }

巴特西

Codeforces 358D Dima and Hares：dp【只考虑相邻元素】

最新文章

热门文章