Number String (ZOJ Problem Set - 3543)

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3543

問題

長さn+1の順列で各公差がqi(+,-もしくはどちらでも良いのどれか)である場合、そのような順列は何通り存在するか？
1<=n<=1000

解法

dpで考える。dp[i][j]は長さi+1の順列で最後が数値jで終わる物の数を表す。公差が+の場合、dp[i+1][0]=0となり他はdp[i+1][j+1]=dp[i+1][j]+dp[i][j]となる。公差が-の場合、逆になりdp[i+1][j]=0でdp[i+1][j+1]+dp[i][j]となる。どちらでも良い場合はもちろん総和になる。