Codeforces Round #208 (Div. 2) D(记忆化搜索)

首先，这题要一眼看出是dp...这种dp[i][0] dp[i][1] 的方法还是蛮经典的之前写好多题都用的了只是以前都是只依赖一种状态，这个题目依赖了前后。然后自己不会写了。参考了Tutorial 写了裸搜吧等于把所有情况搜了出来大概是O(3^n) 或O(4^n) ？返mle..然后改成记忆化搜索。。。其实你去学记忆化不如这样去做题猛然意识到记忆化（也就是对于凡夫俗子还是靠做题）

#include<cstdio>  
#include<algorithm>  
#include<iostream>  
#include<cstring>  
using namespace std;  
typedef long long ll;  
/*  define */  
  
#define sf(a) scanf("%d",&a)  
#define sfs(a) scanf("%s",a)  
#define sfI(a) scanf("%I64d",&a)  
#define pf(a) printf("%d\n",a)  
#define pfI(a) printf("%I64d\n",a)  
#define rep(i,a,b) for(int i=(a);i<=(b);i++)  
#define repd(i,a,b) for(int i=(a);i>=(b);i--)  
#define rep1(i,a,b) for(int i=(a);i<(b);i++)  
#define clr0(a) memset(a,0,sizeof(a))  
#define clr1(a) memset(a,-1,sizeof(a))  
  
/*  define */  
const int N = 3100;  
int a[N],b[N],c[N],dp[N][2];  
int n;  
int dfs(int pos,int fed){  
    int res=0;  
    if(~dp[pos][fed]) return dp[pos][fed];  
    if(pos==n && fed)  
        return b[pos];  
    if(pos==n && !fed)  
        return a[pos];  
    if(!fed)  
        dp[pos][fed]=max(dfs(pos+1,1)+a[pos],dfs(pos+1,0)+b[pos]);  
    else  
        dp[pos][fed]=max(dfs(pos+1,1)+b[pos],dfs(pos+1,0)+c[pos]);  
    return dp[pos][fed];  
}  
int main(){  
    sf(n);  
    rep(i,1,n) sf(a[i]);  
    rep(i,1,n) sf(b[i]);  
    rep(i,1,n) sf(c[i]);  
    clr1(dp);  
    int ans;  
    if(n==1){  
        pf(a[1]);  
        return 0;  
    }  
    ans=max(dfs(2,1)+a[1],dfs(2,0)+b[1]);  
    pf(ans);  
    return 0;  
}

补充：软件开发 , C++ ,