hdu 4999 Overt

题目链接

还是一个很有趣的题。

有一个hash函数，方法为对一个数做至多40次诸如+= -= &= |= ^=..某个数的操作，求hash函数的最大值。

如果没有+=/-=那么这个题是非常轻松加愉快的，每一位是独立的，可以分开考虑。

但有+=/-=就有了进位的问题，就不是完全独立的了，但可以考虑把-=当做+=来看，每个加法是否进位状压一下，但N最大会有40，直接压需要$2^{40}$。

然后发现只要把相邻的加法合并起来，就只有不超过20个加号了。

设f[i][mask]为现在做到第i位，第i位上加法的进位的情况为mask的最大值。只要枚举一下这一位输入0还是1，就可以得到i+1位的进位情况，转移到下一层。

最后就是时限非常紧，而状态非常稀疏，需要好好优化一下。

Written with StackEdit.