codeforces358D Dima and Hares【dp】

从本质入手，这个东西影响取值的就是相邻两个哪个先取

设f[i][0/1]为前i个(i-1,i)中先取i/i-1的值（这里不算上i的贡献

转移就显然了，注意要先复制-inf

#include<iostream>

#include<cstdio>

using namespace std;

const int N=3005;

int n,a[N],b[N],c[N],f[N][2];

int main()

{

	scanf("%d",&n);

	for(int i=1;i<=n;i++)

		scanf("%d",&a[i]);

	for(int i=1;i<=n;i++)

		scanf("%d",&b[i]);

	for(int i=1;i<=n;i++)

		scanf("%d",&c[i]);

	for(int i=0;i<=n+1;i++)

		f[i][0]=f[i][1]=-1e9;

	f[1][0]=0;

	for(int i=2;i<=n+1;i++)

	{

		f[i][0]=max(f[i-1][1]+c[i-1],f[i-1][0]+b[i-1]);

		f[i][1]=max(f[i-1][0]+a[i-1],f[i-1][1]+b[i-1]);

	}

	printf("%d\n",f[n+1][1]);

	return 0;

}

巴特西

codeforces358D Dima and Hares【dp】

最新文章

热门文章