Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
bitset + O2优化 32ms#include <cstdio> #include <bitset> #pragma GCC optimize(2) %:pragma GCC optimize(2) //O2优化,选其一即可。 using namespace std; int read() { int x=0,f=1;char c=getchar(); while (c<'0' || c>'9'){if (c=='-')f=-1;c=getchar();} while (c>='0'&&c<='9'){x=(x<<3)+(x<<1)+c-48;c=getchar();} return x*f; } const int MAXN=1010; const int MAXD=20; int n,d,k,m,ans; bitset<MAXD> cow[MAXN]; bitset<MAXD> down; void dfs(int vis,int now,bitset<MAXD> down) { if (now+d-vis+1<k)return ; if (now==k) { int res=0; bitset<MAXD> a; for (int i=1;i<=n;i++) { a=down&cow[i]; if (a==cow[i])res++; } if (res>ans)ans=res; return ; } for (int i=vis;i<=d;i++) { down[i]=1; dfs(i+1,now+1,down); down[i]=0; } } int main() { n=read();d=read();k=read(); for (int i=1;i<=n;i++) { m=read(); while (m--)cow[i].set(read()); } ans=0; dfs(1,0,down); printf("%d\n",ans); return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator