Ural 1217 Unlucky Tickets 题解
题意
给定$n(2\le n\le 20)$($n$是偶数),求出在所有$n$位数中(可以有前导零),前一半数码的和 与 后一半数码的和相等或在奇数位上的数码的和 与 在偶数位上的数码和相等 的个数。
题解
考虑DP。
$f(i,j,k)$表示在前$i$位,前一半数码的和 减去 后一半数码的和的为$j$,在奇数位上的数码的和 减去 在偶数位上的数码和为$k$ 的个数。
Tip: $j$不可能为负数,而$k$有可能为负数,所以写的时候要把$k$变成非负数,即$f(i,j,k+base)$。
- 初始值:$f(0,0,0)=1$。
状态转移方程:
设当前状态为$f(i,j,k)$,需转移到的状态为$f(i’,j’,k’)$,$i’$位上放的数是$x$。
$i’=i+1$。
若$i’>n/2$且$x>j$($j’$位负数),跳出关于$x$的循环。
若$i’\le n/2$,$j’=j+x$;否则$j’=j-x$。
若$i’\%2=1$,$k’=k+x$;否则$k’=k-x$。
$f(i’,j’,k’)+=f(i,j,k)$即可。
答案:$f(n,0,0)$。
程序
1 | // #pragma GCC optimize(2) |