状态的定义挺奇特的~
发现最终每一个物品一定都会被选走.
令 $f[i][0/1]$ 表示 $a[i]$ 在 $a[i-1]$ 前/后选时 $1$~$(i-1)$ 的最优解.
因为一个数字的价值只由其相邻两边决定~
code:
#include <bits/stdc++.h> #define N 3007 #define ll long long #define setIO(s) freopen(s".in","r",stdin) using namespace std; int n; ll f[N][2],g[N],a[N],b[N],c[N],ans; int main() { // setIO("input"); int i,j; scanf("%d",&n); for(i=1;i<=n;++i) scanf("%lld",&a[i]); for(i=1;i<=n;++i) scanf("%lld",&b[i]); for(i=1;i<=n;++i) scanf("%lld",&c[i]); memset(f, -0x3f, sizeof(f)); f[1][0]=0; for(i=2;i<=n+1;++i) { f[i][0]=max(f[i-1][0]+b[i-1], f[i-1][1]+c[i-1]); f[i][1]=max(f[i-1][0]+a[i-1], f[i-1][1]+b[i-1]); } printf("%lld\n",f[n+1][1]); return 0; }
