2018.09.08bzoj1151:[CTSC2007]动物园zoo（状压dp）

传送门
状压dp好题啊。
可以发现这道题的状压只用压缩5位。
f[i][j]表示当前在第i个位置状态为j的最优值。
显然可以由f[i-1]更新过来。
因此只用预处理在第i个位置状态为j时有多少个小朋友高兴就行了。
代码&＃xff1a;

#include
#define N 50005
using namespace std;
int n,c,f[N][35],cal[N][35],las,ans&＃61;0;
inline int read(){int ans&＃61;0;char ch&＃61;getchar();while(!isdigit(ch))ch&＃61;getchar();while(isdigit(ch))ans&＃61;(ans<<3)&＃43;(ans<<1)&＃43;(ch^48),ch&＃61;getchar();return ans;
}
inline int max(int a,int b){return a>b?a:b;}
int main(){n&＃61;read(),c&＃61;read();for(int i&＃61;1;i<&＃61;c;&＃43;&＃43;i){int a&＃61;read(),b&＃61;read(),c&＃61;read(),tmp1&＃61;0,tmp2&＃61;0;for(int j&＃61;1;j<&＃61;b;&＃43;&＃43;j)tmp1|&＃61;1<<((read()-a&＃43;n)%n);for(int j&＃61;1;j<&＃61;c;&＃43;&＃43;j)tmp2|&＃61;1<<((read()-a&＃43;n)%n);for(int j&＃61;0;j<32;&＃43;&＃43;j)if((j&tmp1)||(~j&tmp2))&＃43;&＃43;cal[a][j];}las&＃61;15;for(int j&＃61;0;j<32;&＃43;&＃43;j){memset(f[0],-0x3f,sizeof(f[0]));f[0][j]&＃61;0;for(int i&＃61;1;i<&＃61;n;&＃43;&＃43;i)for(int k&＃61;0;k<32;&＃43;&＃43;k)f[i][k]&＃61;max(f[i-1][(k&15)<<1],f[i-1][(k&15)<<1|1])&＃43;cal[i][k];ans&＃61;max(ans,f[n][j]);}cout<return 0;
}