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】

原文：https://www.cnblogs.com/lokiii/p/11042228.html