FJWC2016 CodeForces 79D 硬币翻转 【BFS建图+DP】

tonyfang posted @ 2016年2月20日 22:15 in 随笔 with tags c++ OI , 403 阅读
# include <stdio.h>
# include <queue>
# include <algorithm>
# include <string.h>
using namespace std;

const int INF=200011300,MINF=-INF;
queue<int> Q;
const int M=201;
int n,k,m,v[M],a[M],di[M*M],d[M][M],f[4048576];

int main() {
	scanf("%d%d%d",&n,&k,&m);
	for (int i=1;i<=k;++i) {
		scanf("%d",&v[i]);
		v[i+k]=v[i]+1;
	}
	for (int i=1;i<=m;++i) scanf("%d",&a[i]);
	k=k*2; sort(v+1,v+k+1);
	for (int i=1;i<=k;++i) {
		while(!Q.empty()) Q.pop();
		memset(di,-1,sizeof(di));
		Q.push(v[i]); di[v[i]]=0;
		while(!Q.empty()) {
			int top=Q.front();
			Q.pop();
			for (int j=1;j<=m;++j) {
				if(top+a[j]<=n+1 && di[top+a[j]]<0)
					di[top+a[j]]=di[top]+1,Q.push(top+a[j]);
				if(top-a[j]>0 && di[top-a[j]]<0)
					di[top-a[j]]=di[top]+1,Q.push(top-a[j]);
				}
		}
		for (int j=1;j<=k;++j)
			if(di[v[j]]<0) d[i][j]=1000000000;
			else d[i][j]=di[v[j]];
	}
	int maxisize=(1<<k)-1;
	memset(f,63,sizeof(f));
	f[0]=0;
	for (int i=0;i<=maxisize;++i) {
		int dd=1;
		while(i&(1<<(dd-1))) ++dd;
		int now=i|(1<<(dd-1));
		if(dd<k) {
			for (int j=dd+1;j<=k;++j) {
				if(now&(1<<(j-1))) continue;
				int gg=now|(1<<(j-1));
				f[gg]=min(f[gg],f[i]+d[dd][j]);
			}
		}
	}
	printf("%d\n",f[maxisize] >= 1000000000 ? -1 : f[maxisize]);
	return 0;
}
/*
10 8 2
1 2 3 5 6 7 8 9
3 5

Out:2
*/

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter