Question

HDU ACM 2232一天四个不同的机器人a、b、c和d在一张跳舞毯上跳舞，这是一张特殊的跳舞毯，他由4个正方形毯子组

Answer 1

可以用一个四位的五进制表示每块毯上有多少个机器人

把这个四位四进制压缩成一个数j

dp[i][j]代表走了i步之后四块毯上人的状态上j的情况有多少种

最后dp[n][1*5*5*5+1*5*5+1*5+1]就是答案

复杂度100*5的4次方*5的4次方

此题还可以扩展,比如步数N=MOD)path[state][j]-=MOD;

return ;

}

for(i=0;i