Red Huang

Red Huang

Codeforces Round #208 (Div. 2) D. Dima and Hares

只可意會不可言傳的 DP

...

附上官方題解Tutorial

D. Dima and Hares

Let's look at the first hare: we chose them befoe second, or after. If it is chosen after the second, than the solution from the 2nd hare to the last doesn't depend on the first one, otherwise, we will receive the same but before the second hair will be obviously the feed hair. So, we have two dinamics:
1). d_0_i — answer for suffix as a separate task.
2). d_1_i — answer for suffix if the previous hair for this suffix is feed already.
Movements:
d_0_n  =  an
d_1_n  =  bn
d_0_i  =  max(ai  +  d_1_i  +  1,  bi  +  d_0_i  +  1)
d_1_i  =  max(bi  +  d_1_i  +  1,  ci  +  d_0_i  +  1)

//  
//        GGGGGGGGGGGGG        CCCCCCCCCCCCC               AAA  
//     GGG::::::::::::G     CCC::::::::::::C              A:::A  
//   GG:::::::::::::::G   CC:::::::::::::::C             A:::::A  
//  G:::::GGGGGGGG::::G  C:::::CCCCCCCC::::C            A:::::::A  
// G:::::G       GGGGGG C:::::C       CCCCCC           A:::::::::A  
//G:::::G              C:::::C                        A:::::A:::::A  
//G:::::G              C:::::C                       A:::::A A:::::A  
//G:::::G    GGGGGGGGGGC:::::C                      A:::::A   A:::::A  
//G:::::G    G::::::::GC:::::C                     A:::::A     A:::::A  
//G:::::G    GGGGG::::GC:::::C                    A:::::AAAAAAAAA:::::A  
//G:::::G        G::::GC:::::C                   A:::::::::::::::::::::A  
// G:::::G       G::::G C:::::C       CCCCCC    A:::::AAAAAAAAAAAAA:::::A  
//  G:::::GGGGGGGG::::G  C:::::CCCCCCCC::::C   A:::::A             A:::::A  
//   GG:::::::::::::::G   CC:::::::::::::::C  A:::::A               A:::::A  
//     GGG::::::GGG:::G     CCC::::::::::::C A:::::A                 A:::::A  
//        GGGGGG   GGGG        CCCCCCCCCCCCCAAAAAAA                   AAAAAAA  
#include <iostream>  
#include <cstdio>  
#include <cstring>  
#include <algorithm>  
#include <cmath>  
#include <climits>  
#include <vector>  
#include <set>  
#include <map>  
#include <queue>  
#include <cctype>  
#include <utility>  
#include <ctime>  
using namespace std;  
#ifdef DEBUG  
#define VAR(a,b) decltype(b) a=(b)  
#define debug(...) printf("DEBUG: "),printf(\_\_VA\_ARGS\_\_)  
#define gettime() end\_time=clock();printf("now running time is %.7f\\n",(float)(end\_time - start\_time)/CLOCKS\_PER\_SEC);  
#else  
#define VAR(a,b) \_\_typeof(b) a=(b)  
#define debug(...)  
#define gettime()  
#endif  
typedef unsigned int uint;  
typedef long long int Int;  
typedef unsigned long long int UInt;  
#define Set(a,s) memset(a,s,sizeof(a))  
#define Write(w) freopen(w,"w",stdout)  
#define Read(r) freopen(r,"r",stdin)  
#define Pln() printf("\\n")  
#define I\_de(x,n)for(int i=0;i<n;i++)printf("%d ",x\[i\]);Pln()  
#define De(x)printf(#x"%d\\n",x)  
#define For(i,x)for(int i=0;i<x;i++)  
#define CON(x,y) x##y  
#define Pmz(dp,nx,ny)for(int hty=0;hty<ny;hty++){for(int htx=0;htx<nx;htx++){\\  
    printf("%d ",dp\[htx\]\[hty\]);}Pln();}  
#define M 3005  
#define PII pair<int,int\>  
#define PB push\_back  
#define oo INT\_MAX  
#define Set\_oo 0x3f  
#define FOR(a,b) for(VAR(a,(b).begin());a!=(b).end();++a)  
#define eps 1e-6  
#define X first  
#define Y second  
clock\_t start\_time=clock(), end\_time;  
bool xdy(double x,double y){return x>y+eps;}  
bool xddy(double x,double y){return x>y-eps;}  
bool xcy(double x,double y){return x<y-eps;}  
bool xcdy(double x,double y){return x<y+eps;}  
int min3(int x,int y,int z){  
    int tmp=min(x,y);  
    return min(tmp,z);  
}  
int max3(int x,int y,int z){  
    int tmp=max(x,y);  
    return max(tmp,z);  
}  
int a\[M\],b\[M\],c\[M\];  
int dp\[M\]\[3\];  
int main() {  
    ios\_base::sync\_with\_stdio(0);  
    int n;  
    while(~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\]);  
        if(n==1){  
            printf("%d",a\[1\]);  
            continue;  
        }else{  
            dp\[2\]\[0\]=b\[1\];  
            dp\[2\]\[1\]=a\[1\];  
            //dp\[i\]\[0\]代表先餵了i再餵i-1  
            //dp\[i\]\[1\]代表先餵了i-1再餵i  
            for(int i=3;i<=n;i++){  
                dp\[i\]\[0\]=max(dp\[i-1\]\[0\]+b\[i-1\],dp\[i-1\]\[1\]+c\[i-1\]);  
                //餵的順序是\[i\] \[i-1\] \[i-2\]  \[i-2\] \[i\] \[i-1\]  
                dp\[i\]\[1\]=max(dp\[i-1\]\[0\]+a\[i-1\],dp\[i-1\]\[1\]+b\[i-1\]);  
                //餵的順序是\[i-1\] \[i-2\] \[i\]  \[i-2\] \[i-1\] \[i\]  
            }  
            int ans=max(dp\[n\]\[0\]+a\[n\],dp\[n\]\[1\]+b\[n\]);  
            printf("%d\\n",ans);  
        }  
  
    }  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
}  

Loading...
Ownership of this post data is guaranteed by blockchain and smart contracts to the creator alone.