标题字数限制输不完!!!!!!!

标题字数限制输不完!!!!!!!

标题字数限制输不完!!!!!!!

题目本来叫

Basketball Exercise

题意

很明显的一道DP题,但是做了我一个多小时,归根到底就是没有理解题意英语太差and翻译出锅

咳咳

认真想一想

每一行n个人,每一列两个人,每一行连续选择两个人(也就是说在这一行选了人的话下一次一定要换行选人),求总体最有解

dp[i][j],i毫无疑问是这两个人的编号,j的话有三个取值0,1,2

0代表这一列的两个人都不选
1代表选上面这行的人
2代表选下面这行的人

这样整个转移方程就逐渐清晰明了了

对于第i列而言,我们能做出的决策无非就三种:1.选上面2.选下面.3.都不选

对于dp[i][0] 来说,它当前的状态可以有三个来源dp[i-1][0],dp[i-1][1],dp[i-1][2]
因为无论在上一个列(i-1)做了什么,我们都可以选择在第i列什么都不选.
所以dp[i][0]=max(dp[i-1][0],max(dp[i-1][1],dp[i-1][2]));

对于dp[i][1] 来说,既然这一次选择了上面这行的人,说明上一次就不可能选择上面这行的人了.
所以dp[i][1]的状态来源有两个dp[i-1][0],dp[i-1][2]
方程:dp[i][1]=max(dp[i-1][0],dp[i-1][2])+h[i][1];

对于dp[i][2] 来说,既然这一次选择了下面这行的人,说明上一次就不可能选择下面这行的人了.
与dp[i][1]同理,状态来源有两个dp[i-1][0],dp[i-1][1]
方程:dp[i][2]=max(dp[i-1][0],dp[i-1][1])+h[i][2];

核心方程说完,下面就是代码了

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define maxn 220000
#define rg register
inline ll read()
{
    ll x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9')
    {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c<='9'&&c>='0')
    {
        x=(x<<1)+(x<<3)+(c^48);
        c=getchar();
    }
    return x*f;
}
int n;
ll h[maxn][3];
ll dp[maxn][3];//0--当前两个都不选 1--选h1 2--选h2
inline ll max(ll a,ll b)
{
    if(a>b) return a;
    return b;
} 
int main()
{
    n=read();
    for(rg int i=1;i<=n;++i) h[i][1]=read();
    for(rg int i=1;i<=n;++i) h[i][2]=read();    
    dp[1][0]=0,dp[1][1]=h[1][1],dp[1][2]=h[1][2];
    for(rg int i=2;i<=n;++i)
    {
        dp[i][0]=max(dp[i-1][0],max(dp[i-1][1],dp[i-1][2]));
        dp[i][1]=max(dp[i-1][0],dp[i-1][2])+h[i][1];
        dp[i][2]=max(dp[i-1][0],dp[i-1][1])+h[i][2];
    }
    cout<<max(dp[n][0],max(dp[n][1],dp[n][2]));
}