题解 CF1195C 【Basketball Exercise】
小黑AWM
2019-07-18 09:21:00
简单的线性的DP，一眼看出状态后很容易可以写掉，但是题意可能会有导向性错误导致想到 $O(n^2)$ 的算法。
约定：记 $h(x,y)$ 为第 $x$ 列，第 $y$ 行的人的身高。
第 $i$ 列我们考虑有三种状态：选第一个，选第二个，不选。由于题意限制，我们需要考虑是否连续两个选的在同一行。
不难发现除了当前这列和之前这列我们需要考虑，更前面的状态都已经没有用了，那么这满足了无后效性的要求。
我们给出最大的子方案一定能使的总方案最大，所以也满足最优子结构的性质。
根据之前的考虑设计状态 $f(i,\space k)$ 表示选到第 $i$ 列，每列选了第 $k$ 行的人时的最大身高和，当 $k=0$ 时表示这列不选。
由状态直接得到状态转移方程，不需要优化可以直接线性DP。
$$f(i ,k) = max\{f(i-1,j)+h(i,k)\},j\in \{0,1,2\}$$
且 $j$ 和 $k$ 应满足 $j \not = k$ 或 $j=k=0$
那么最终答案就是 $max\{f(n,0),f(n,1),f(n,2)\}$ 实现并没有难度。
```cpp
/*
* Author: xiaohei_AWM
* Date: 7.17
* Mutto: Face to the weakness, expect for the strength.
*/
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
#define reg register
#define endfile fclose(stdin);fclose(stdout);
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef std::pair<int,int> pii;
typedef std::pair<ll,ll> pll;
namespace IO{
char buf[1<<15],*S,*T;
inline char gc(){
if (S==T){
T=(S=buf)+fread(buf,1,1<<15,stdin);
if (S==T)return EOF;
}
return *S++;
}
inline int read(){
reg int x;reg bool f;reg char c;
for(f=0;(c=gc())<'0'||c>'9';f=c=='-');
for(x=c^'0';(c=gc())>='0'&&c<='9';x=(x<<3)+(x<<1)+(c^'0'));
return f?-x:x;
}
inline ll readll(){
reg ll x;reg bool f;reg char c;
for(f=0;(c=gc())<'0'||c>'9';f=c=='-');
for(x=c^'0';(c=gc())>='0'&&c<='9';x=(x<<3)+(x<<1)+(c^'0'));
return f?-x:x;
}
}
using namespace IO;
const int maxn = 1e5 + 10;
int n;//f[i][j]表示选到第i个人，那人是j状态的最大答案
ll h[3][maxn], f[maxn][3];
int main(){
n = read();
for(int i = 1; i <= n; i++) h[1][i] = read();
for(int i = 1; i <= n; i++) h[2][i] = read();
for(int i = 1; i <= n; i++){
for(int j = 0; j <= 2; j++){
for(int k = 0; k <= 2; k++){
if(j == k && j != 0) continue;
f[i][j] = max(f[i][j], f[i-1][k] + h[j][i]);
}
}
}
cout << max(f[n][0], max(f[n][1], f[n][2])) << endl;
return 0;
}
```