Category: 状压DP

题目传送门：http://oi.cyo.ng/wp-content/uploads/2016/11/20161108.pdf

还好之前做过类似的题目，要不然肯定做不起了 QAQ
原题在这里：http://oi.cyo.ng/?p=339

1k以内右168个素数，但第12个素数就大于33了
换一句话来说，第12~168个素数不会不会互相干扰

于是前11个素数拿来暴力，后面的素数直接贪心即可

#include<bits/stdc++.h>
#define LL long long
#define max(x,y) ((x)>(y)?(x):(y))
using namespace std;

const int N = 1001;
const int M = 200;
const int MX = 2100;

bitset<N> vec[M],vis,ans;
int n,m,BAS[N],vout,sign,f[2][MX],w,p;

inline int read() {
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

inline void DFS(int t) {
	if (!sign && t == m+1) {
		vout = max(vout, (int)vis.count());
	} else if (sign && t == 12) {
		int ret = 0;
		for (int i=1;i<=11;i++) {
			if (ans[i]) {
				ret += (1<<(i-1));
			}
		}
		f[p][ret] = max(f[p][ret],(int)vis.count());
	} else {
		DFS(t + 1);
		for (int i=1;i*BAS[t]<=n;i++) 
			vis[i*BAS[t]] = vis[i*BAS[t]] ^ 1;
		ans[t] = 1;
		DFS(t + 1);
		for (int i=1;i*BAS[t]<=n;i++) 
			vis[i*BAS[t]] = vis[i*BAS[t]] ^ 1;
		ans[t] = 0;
	}
}

int main() {
	freopen("prime.in","r",stdin);
	freopen("prime.out","w",stdout);
	for (int T=read(),cnt;T;T--,vout=0,sign=0) {
		n = read(); m = read();
		if (m > 12) {
			w = 1; p = 0;
			memset(f,0,sizeof(f));
			vis.reset(); ans.reset();
			
			for (int i=1;i<=m;i++) 
				BAS[i] = read();
			sort(BAS+1,BAS+1+m);
			sign = 1; DFS(1);
			 
			for (int i=12;i<=m;i++,w^=1,p^=1) {
				memset(f[w],0,sizeof(f[w]));
				for (int j=0,sta,tmp;j<=2047;j++) {
					tmp = 0;
					for (int k=1,lim=n/BAS[i];k<=lim;k++) {
						sta = 0; 
						for (int x=1,cur=1;x<=11;x++,cur<<=1) {
							if ((j&cur) && k % BAS[x] == 0) 
								sta ^= 1;
						}
						if (sta) tmp--;
						else tmp++;
					}	
					f[w][j] = f[p][j] + max(0, tmp);
				}
			}
			for (int i=0;i<=2047;i++) 
				vout = max(f[p][i], vout);
			printf("%d\n",vout);
		} else {
			vis.reset();
			for (int i=1;i<=m;i++)
				BAS[i] = read();
			sign = 0; DFS(1);
			printf("%d\n",vout);
		}
	}
	return 0;
}

题目传送门：http://42.247.7.121/zh/Problem/Details/2922
离线版题目：http://paste.ubuntu.com/23198035/
数据生成器：http://paste.ubuntu.com/23198038/

这题真的是好妙！点个大赞！
题解让我们召唤黄学长：http://hzwer.com/3308.html
另外，我的这份代码的复杂度多了一个k，要想速度快就去抄黄学长的代码吧！

#include<bits/stdc++.h>
#define LL long long
using namespace std;

int n,m,k,cnt,dis[10010],sz[200],pos[30],f[1200000],cost[30][30]; 
queue<int> que;

inline int read(){
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

inline void BFS(int W, int num) {
	memset(dis,127,sizeof(dis));
	que.push(W); dis[W] = 0;
	
	while (!que.empty()) {
		int w = que.front(); que.pop();
		for (int i=1;i<=m;i++) {
			if (w+sz[i] <= n+1 && dis[w+sz[i]] > dis[w]+1)  dis[w+sz[i]] = dis[w]+1, que.push(w+sz[i]);
			if (w-sz[i] >= 1 && dis[w-sz[i]] > dis[w]+1)  dis[w-sz[i]] = dis[w]+1, que.push(w-sz[i]);
		}
	} 
	for (int i=1;i<=cnt;i++) cost[num][i] = dis[pos[i]];
}

int main(){
	n = read(); k = read(); m = read();
	for (int i=1;i<=k;i++) dis[read()] = 1;
	for (int i=1;i<=m;i++) sz[i] = read(); sort(sz+1,sz+1+m); m = unique(sz+1,sz+1+m) - sz - 1;
	for (int i=1;i<=n+1;i++) if (dis[i] + dis[i-1] == 1) pos[++cnt] = i;
	for (int i=1;i<=cnt;i++) BFS(pos[i],i); 
	memset(f,127,sizeof(f));
	f[(1<<cnt)-1] = 0;
	for (int w=(1<<cnt)-1;w;w--) if (f[w] < 1e9) 
		for (int i=1;i<=cnt;i++) if (w&(1<<i-1)) for (int j=i+1;j<=cnt;j++) if (w&(1<<j-1) && cost[i][j] < 1e9)
			f[w^(1<<i-1)^(1<<j-1)] = min(f[w^(1<<i-1)^(1<<j-1)],f[w]+cost[i][j]); 
	printf("%d\n",f[0]>1e9?-1:f[0]);
	return 0;
}

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=4626
数据生成器：http://paste.ubuntu.com/23171656/

这题，是我到目前为止做过的最恶心的题目
没有之一

如果击中，那么三级狗一定在连续$a_i$个回合里没有转向，并且有一个回合没有动
那么$DP$的时候记录一下最近$a_i$次的移动情况即可
chenyushuo提供的资料：http://pan.baidu.com/s/1kVg3uvl

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int MOD = 1000000007;

int X,Y,OP,n,m,T,vis[30][30],hit[60][13][13],f[2][22][22][5][21][13],W=1,P;
int dx[]={0,1,0,-1,0},dy[]={0,0,1,0,-1},vout[22][22],del[60];
char pat[30];

int main(){
	cin>>n>>m>>T; 
	for (int i=1;i<=n;i++) {
		scanf("%s",pat+1);
		for (int j=1;j<=m;j++) 
			if (isdigit(pat[j])) vis[i][j] = 1, f[P][i][j][pat[j]-'0'+1][0][0] = 1;
			else if (pat[j] == '.') vis[i][j] = 1;
	} 
	for (int i=1;i<T;i++) cin>>del[i];
	for (int k=0;k<=T;k++) for (int go=0;go<=12;go++) for (int dly=0;dly<=go;dly++)
		for (int w=dly;w<go;w++) if (k-w >= 1 && del[k-w] == w+1) hit[k][go][dly] = 1;
	for (int k=1;k<=T;k++,W^=1,P^=1,memset(f[W],0,sizeof(f[W]))) for (int j=1;j<=m;j++) for (int i=1;i<=n;i++) 
		if (vis[i][j]) for (int to=1;to<=4;to++) for (int go=0;go<=12;go++) for (int dl=0,tmp;dl<=12;dl++) {
			if (!(tmp=f[P][i][j][to][go][dl])) continue;
			if (!hit[k-1][dl][0]) (f[W][i][j][to][min(12,dl+1)][0] += tmp) %= MOD;
			if (vis[i+dx[to]][j+dy[to]] && !hit[k-1][go][dl]) 
				(f[W][i+dx[to]][j+dy[to]][to][min(12,go+1)][min(12,dl+1)] += tmp) %= MOD;
			for (int op=1;op<=4;op++) if (op != to && vis[i+dx[op]][j+dy[op]]) 
				(f[W][i+dx[op]][j+dy[op]][op][0][0] += tmp) %= MOD;
	}
	for (int j=1;j<=m;j++) for (int i=1;i<=n;i++) for (int to=1;to<=4;to++) 
		for (int go=0;go<=12;go++) for (int dl=0;dl<=12;dl++) 
			(vout[i][j] += f[P][i][j][to][go][dl]) %= MOD;
	for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) 
		printf("%d%c",vout[i][j],j==m?'\n':' ');
	return 0;
}

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=2595
数据生成器：http://paste.ubuntu.com/23070779/

斯坦纳树第一题！ 撒花~ *★,°*:.☆(￣▽￣)/$:*.°★* 。
然而感觉斯坦纳树，撑死了算一类DP问题，为什么要叫算法呢QAQ
其实斯坦纳树，说白了就是一个状压DP？

题解的话，让我们召唤神犇：http://www.cnblogs.com/lidaxin/p/5299762.html

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define id(x,y) (((y)-1)*n+(x))
using namespace std;

const int MAXN = 19*19;
const int N = 2500;
const int INF = 0x3f3f3f3f;

int n,m,cnt,mat[MAXN],f[MAXN][N],num[MAXN],X,Y,vis[MAXN][N],pv,avl[MAXN];
queue<pair<int,int> > que;
pair<int,int> from[MAXN][N];

inline int read(){
	char c=getchar(); int ret=0;
	while (c<'0'||c>'9') c=getchar();
	while (c<='9'&&c>='0') ret=ret*10+c-'0',c=getchar();
	return ret;
}

inline void rev(int w){
	Y = w / n + 1;
	X = w - (Y-1)*n;
	if (!X) X = n, Y--;
}

inline void update(int op, int nv, int pos, int w){
	if (f[pos][w] > nv) {
		f[pos][w] = nv;
		from[pos][w] = make_pair(op,w);
		if (!vis[pos][w]) vis[pos][w] = 1, que.push(make_pair(pos,w));
	}
}

inline void SPFA(){
	while (!que.empty()) {
		rev(que.front().first);
		int x=X, y=Y, w=que.front().second, pos=que.front().first; 
		vis[pos][w] = 0; que.pop();
		if (x > 1) update(pos,f[pos][w]+mat[id(x-1,y)],id(x-1,y),w);
		if (y > 1) update(pos,f[pos][w]+mat[id(x,y-1)],id(x,y-1),w);
		if (x < n) update(pos,f[pos][w]+mat[id(x+1,y)],id(x+1,y),w);
		if (y < m) update(pos,f[pos][w]+mat[id(x,y+1)],id(x,y+1),w);
	}
}

inline void Steiner_Tree(){
	for (int w=1,lim=1<<cnt;w<lim;w++) {
		for (int j=1;j<=m;j++) for (int i=1;i<=n;i++) {
			for (int k=w&(w-1);k;k=w&(k-1)) {
				int tmp = f[id(i,j)][k] + f[id(i,j)][w^k] - mat[id(i,j)];
				if (f[id(i,j)][w] > tmp) f[id(i,j)][w] = tmp, from[id(i,j)][w] = make_pair(id(i,j),k);		
			}
			if (f[id(i,j)][w] != INF) que.push(make_pair(id(i,j),w)), vis[id(i,j)][w] = 1;
		} SPFA();
	}
}

void Mark_Ans(pair<int,int> tmp){
	int pos=tmp.first, w = tmp.second; if (!pos) return; 
	rev(pos); int x = X, y = Y; avl[id(x,y)] = 1; 
	Mark_Ans(from[pos][w]); 
	if (from[pos][w].first == pos) Mark_Ans(make_pair(id(x,y),w-from[pos][w].second));
	
}

int main(){
	m = read(); n = read();
	for (int j=1;j<=m;j++) for (int i=1;i<=n;i++) {
		memset(f[id(i,j)],0x3f,sizeof(f[id(i,j)]));
		f[id(i,j)][0] = 0; mat[id(i,j)] = read(); 
		if (!mat[id(i,j)]) f[id(i,j)][1<<cnt++] = 0, pv = id(i,j);
	} 
	Steiner_Tree(); Mark_Ans(make_pair(pv,(1<<cnt)-1));
	printf("%d\n",f[pv][(1<<cnt)-1]);
	for (int j=1;j<=m;j++) {
		for (int i=1;i<=n;i++) 
			if (!mat[id(i,j)]) putchar('x');
			else if (avl[id(i,j)]) putchar('o');
			else putchar('_');
		putchar('\n');
	}
	return 0;
}

题目传送门：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可以暴力过的样子
有没有同学有空写写啊！