UVa11420 - Chest of Drawers(动态规划)

#include <cstdio>#include <cstring>usingnamespacestd;
typedeflonglongLL;
constintN=70;
constintM=2;
LLmemo[N][M][N];
intn, s;
boolinput();
voidsolve();
LLdfs(intdep, intlock, intseq);
intmain()
{
#ifndef ONLINE_JUDGEfreopen("d:\\OJ\\uva_in.txt", "r", stdin);
#endifwhile (input()) {
solve();
    }
return0;
}
boolinput()
{
scanf("%d%d", &n, &s);
if (n<0&&s<0) returnfalse;
returntrue;
}
LLdfs(intdep, intlock, intseq)
{
if (dep==n) returnseq==s;
LL&ans=memo[dep][lock][seq];
if (ans!=-1) returnans;
ans=0;
if (!lock) {
ans+=dfs(dep+1, 1, seq) +dfs(dep+1, 0, seq); 
    } else {
ans+=dfs(dep+1, 1, seq+1) +dfs(dep+1, 0, seq);
    }
returnans;
}
voidsolve()
{
memset(memo, -1, sizeof(memo));
printf("%lld\n", dfs(1, 0, 0) +dfs(1, 1, 1));
}