CodeForces 1195C Basketball Exercise （线性DP）
思路：
一眼的dp
dp[i] [j]表示选到第i列时第j行的身高之和(j=0,1)
答案就是max(dp[n] [0],dp[n] [1]);
划分界限为这一列是否选，不选的话从上一列的同一行转移，选的话从上一列的不同行转移。
代码：
#include<bits/stdc++.h> using namespace std; typedef long long ll; #define x first #define y second const int maxn=1e5+10; ll dp[maxn][2]; pair<ll,ll>p[maxn]; int main(){ int n;cin>>n; for(int i=1;i<=n;i++) cin>>p[i].x; for(int i=1;i<=n;i++) cin>>p[i].y; dp[1][0]=p[1].x;dp[1][1]=p[1].y; for(int i=2;i<=n;i++){ dp[i][0]=max(dp[i-1][0],dp[i-1][1]+p[i].x); dp[i][1]=max(dp[i-1][1],dp[i-1][0]+p[i].y); } cout<<max(dp[n][0],dp[n][1])<<endl; return 0; }
