[关闭]
@ysner 2018-05-19T15:16:43.000000Z 字数 1048 阅读 1782

[APIO2007]动物园

状压DP DP


题面

戳我

解析

注意到每个小朋友只能看到个动物,可以状压
我们可以对每个小朋友预处理一下他面对每种状态会不会满意。
然后就可枚举动物数和当前状态进行状压


有点绕脑的是这是个环
我们在开始时规定号位(即号位)的某一状态可以转移,最后只统计号位上这一状态的答案即可。

  1. #include <iostream>
  2. #include <cstring>
  3. #include <cstdio>
  4. #define check(st) ((st&l)||(~st&d))
  5. using namespace std;
  6. template <typename Tp> inline void read(Tp &x)
  7. {
  8. x=0;
  9. char ch=getchar();
  10. while(ch<'0'||ch>'9') ch=getchar();
  11. while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
  12. }
  13. const int maxn=50010;
  14. int n,m,ans,f[maxn][40],num[maxn][40];
  15. inline int max(int x,int y){return x>y?x:y;}
  16. void input()
  17. {
  18. int a,b,c,l,d,t;
  19. read(n);read(m);
  20. for(int i=1;i<=m;i++)
  21. {
  22. read(a);read(b);read(c);
  23. l=d=0;
  24. for(int j=1;j<=b;j++)
  25. {read(t);t=(t-a+n)%n;l|=1<<t;}
  26. for(int j=1;j<=c;j++)
  27. {read(t);t=(t-a+n)%n;d|=1<<t;}
  28. for(int j=0;j<32;j++)
  29. if(check(j))
  30. num[a][j]++;
  31. }
  32. }
  33. int main()
  34. {
  35. input();
  36. for(int i=0;i<32;i++)
  37. {
  38. memset(f[0],128,sizeof(f[0]));
  39. f[0][i]=0;
  40. for(int j=1;j<=n;j++)
  41. for(int s=0;s<32;s++)
  42. f[j][s]=max(f[j-1][(s&15)<<1],f[j-1][(s&15)<<1|1])+num[j][s];
  43. if(ans<f[n][i])
  44. ans=f[n][i];
  45. }
  46. printf("%d\n",ans);
  47. return 0;
  48. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注