ZJU/ZOJ 2042 Divisibility 解题报告

题目大意是在给出的n个数间添加+或-，问能否使等式结果能够被k整除。

类似于背包的做法，利用到上一个数为止的等式的可能余数来得到到当前数为止的等式的可能余数。状态转移方程是f[i,j]=f[i-1,(j-x+k) mod k] or f[i-1,(j+x) mod k](1<=i<=n,0<=j<k);f[i,j]表示到第i位为止的等式，余数为j的情况是否可能，其中x是当前位的数。因为f[i]的状态只与f[i-1]有关，所以可以用滚动数组优化。最后检查一下f[n,0]的状态即可判断是否能被k整除了。GDOI 2000有一道题原题就是这题……

3021545 2008-08-04 19:05:38 Accepted 2042 FPC 00:00.40 408K IwfWcf