CF358D Dima and Hares dp

状态的定义挺奇特的~ 

发现最终每一个物品一定都会被选走. 

令 $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
",f[n+1][1]); 
	return 0; 
}