题目传送门:http://pan.baidu.com/s/1eR1sqXk
离线版题目:http://paste.ubuntu.com/18699825/
数据传送门:http://pan.baidu.com/s/1o8pgYZg
这个题目,暴力的状压很容易想到,然而质因数太多,数组开不下 QAQ
于是考试的时候,码个暴力就闪人了。一看题解,真的是好妙啊!o( ̄▽ ̄)ブ
我们只拆分33以内的质因数,这里只有12个,可以承受。
这么干,还有一个好处:对于一个1k以内的数,超过33的质因数只可能有一个
也就是说,我们对于任意一个数,分两种情况讨论:
1)只有33以内的质因数:这样的话,直接暴力转移即可
2)有33以上的质因数:将拥有相同的、大于33的质因数的数存成一组,像分组背包一样一起转移
因为大于33的质因数只可能有一个,而相同的存在了一起,所以只要保证小于34的质因数不重合即可
此题真的是妙啊!
#include<iostream> #include<cstdio> using namespace std; const int MAXN = 5000; const int LIM = 4500; const int N = 12; int sed[]={0,2,3,5,7,11,13,17,19,23,29,31,33}; int n,que[MAXN][MAXN],cnt[MAXN]; int t1[MAXN],t2[MAXN],*f,*g; inline int read(){ char c=getchar(); int buf=0,f=1; while (c<'0'||c>'9'){if(c=='-')f-1;c=getchar();} while (c<='9'&&c>='0'){buf=buf*10+c-'0';c=getchar();} return buf*f; } int main(){ freopen("prime.in","r",stdin); freopen("prime.out","w",stdout); n = read(); f=t1; g=t2; for (int i=1,a;i<=n;i++){ a = read(); int tmp = a, buf = 0; for (int i=1;i<=N;i++) if (!(tmp%sed[i])) { while (!(tmp%sed[i])) tmp /= sed[i]; buf |= 1<<(i-1); } if (tmp != 1) que[tmp][++cnt[tmp]] = buf; else for (int i=1;i<=LIM;i++) if (!(i&buf)) f[i|buf] = max(f[i|buf], f[i]+1); } for (int i=1;i<=1000;i++){ for (int k=1;k<=LIM;k++) g[k] = f[k]; for (int j=1;j<=cnt[i];j++) for (int k=1;k<=LIM;k++) if (!(k&que[i][j])) g[k|que[i][j]] = max(g[k|que[i][j]], f[k]+1); swap(g,f); } int vout = 1; for (int i=1;i<=LIM;i++) vout = max(vout, f[i]); printf("%d\n",vout); return 0; }
—————————— UPD 2017.2.1 ——————————
总感觉这个题DLX可以暴力过的样子
有没有同学有空写写啊!
It?¦s actually a cool and helpful piece of information. I?¦m happy that you just shared this useful info with us. Please keep us up to date like this. Thanks for sharing.
It’s arduous to seek out educated people on this topic, but you sound like you already know what you’re speaking about! Thanks