Codeforces 268D

기둥이 하나 있는데 점마다 꽂을 수 있고 막대기 하나만 있고 막대기의 방향은 네 가지가 있다.처음에는 임의의 방향으로 위로 올라갈 수 있고, 그 다음에 원래의 방향에 따라 끊임없이 위로 올라갈 수 밖에 없다...dp[i][a1][a2][a3][a4]는 현재 이미 꽂은 i와 몽둥이가 a1에 도달할 수 있는지를 나타낸다. 다른 세 방향의 몽둥이와 i와 몽둥이의 거리는 각각 a2, a3, a4이다.

#include
#include
#include
using namespace std;
const int mod=1e9+9;
typedef __int64 LL;
LL dp[1010][2][31][31][31];
void fm(LL &x){
    if(x>mod)x-=mod;
}
int main(){
    #ifdef DouBi
    freopen("in.cpp","r",stdin);
    #endif // DouBi
    int n,h;while(scanf("%d%d",&n,&h)!=EOF){
        memset(dp,0,sizeof(dp));
        dp[0][0][0][0][0]=1;
        LL val;
        for(int i=0;ifor(int a=0;a<=1;a++){
                for(int b=0;b<=h;b++){
                    for(int c=0;c<=h;c++){
                        for(int d=0;d<=h;d++)if(val=dp[i][a][b][c][d]){
                            dp[i+1][a][b+11:h][c+11:h][d+11:h]+=dp[i][a][b][c][d];   fm(dp[i+1][a][b+11:h][c+11:h][d+11:h]);
                            dp[i+1][b+1<=h?0:1][c+11:h][d+11:h][a?h:1]+=dp[i][a][b][c][d];fm(dp[i+1][b+1<=h?0:1][c+11:h][d+11:h][a?h:1]);
                            dp[i+1][c+1<=h?0:1][d+11:h][a?h:1][b+11:h]+=dp[i][a][b][c][d];fm(dp[i+1][c+1<=h?0:1][d+11:h][a?h:1][b+11:h]);
                            dp[i+1][d+1<=h?0:1][a?h:1][b+11:h][c+11:h]+=dp[i][a][b][c][d];fm(dp[i+1][d+1<=h?0:1][a?h:1][b+11:h][c+11:h]);
                        }
                    }
                }
            }
        }
        //printf("%I64d
",dp[1][0][1][1][1]);
        LL ans=0;
        for(int a=0;a<=1;a++){
            for(int b=0;b<=h;b++){
                for(int c=0;c<=h;c++){
                    for(int d=0;d<=h;d++){
                        if(!a||b//if(n==2&&dp[n][a][b][c][d])printf("%d %d %d %d %I64d
",a,b,c,d,dp[n][a][b][c][d]);
                            ans+=dp[n][a][b][c][d];fm(ans);
                        }
                    }
                }
            }
        }
        printf("%I64d
",ans);
    }
    return 0;
}