题目内容

小红每天都会去$n$个地方采蘑菇，这些地点连成一条直线编号为$1$~$n$

如果小红今天在$i$地采了蘑菇，那么他第二天将不能在$i-1$,$i$,$i+1$这三地采蘑菇。

现在给你$m$天每天每个地点产生的蘑菇数量，小红每天可以选择多个地方采蘑菇。你能求出小红最多能采多少蘑菇吗？

思路：状态压缩动态规划

大家需要先学习掌握二进制集合操作

dp[i][j]代表第i天选了状态为j的地方采蘑菇能得到的最大值，然后二重循环枚举当天的状态和上一天的状态，检查合法的取max转移

具体的，如果k的第i位为1，那么j的第i-1位和第i+1位不能为1