codeforces Round #574(Div.2) Problem-C. Basketball Exercise（DP）

题目链接：http://codeforces.com/contest/1195/problem/C

 

 

题意：

有两排人每排n个，从左到右为1 - n, 然后从中选出任意个人，但是又一定的规则

1.连续的两个人不能再同一行
2.下一个人的下标一定要比前一个大

问能选出来的人的身高最多又多大？

分析：

典型的动态规划，我们把在每一列选或者不选看作一种状态，那么这种状态又三种情况

1.不选
2.从第一行选
2.从第二行选

状态转移方程就是

dp[i][0] = max(dp[i-1][1], dp[i-1][2]);
dp[i][1] = max(dp[i-1][0], dp[i-1][2]);
dp[i][2] = max(dp[i-1][0], dp[i-1][1]);

code：

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;
const int MAXN = 1e5+7;
typedef long long LL;

LL people[3][MAXN];
LL dp[MAXN][3];

int main()
{
    int n;
    while(scanf("%d", &n) != EOF)
    {
        for(int i=1; i<=2; i++)
        {
            for(int j=1; j<=n; j++)
            {
                scanf("%lld", &people[i][j]);
            }
        }

        memset(dp, 0, sizeof(dp));
        for(int i=1; i<=n; i++)
        {
            // printf("Here\n");
            dp[i][0] = max(dp[i-1][1], dp[i-1][2]);
            dp[i][1] = max(dp[i-1][0], dp[i-1][2]) + people[1][i];
            dp[i][2] = max(dp[i-1][0], dp[i-1][1]) + people[2][i];
        }

        // for(int i=0; i<=2; i++)
        // {
        //     for(int j=0; j<=n; j++)
        //     {
        //         printf("%d ", dp[i][j]);
        //     }
        //     printf("\n");
        // }

        printf("%lld\n", max(dp[n][0], max(dp[n][1], dp[n][2])));
    }
    

    




    return 0;
}