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

tonyfang posted @ 2016年2月20日 22:15 in 随笔 with tags c++ OI , 778 阅读
# 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
*/
edpost.in 说:
2023年6月18日 16:00

edpost is an initiative of professional writers who have banded together to provide devoted news coverage of current events in India. Our team is made up of professional writers and citizen journalists with a wide edpost.in range of journalism interests who are passionate about reporting Education Updates with transparency in the general public interest.

mon activité google 说:
2023年7月13日 01:05

Vous pouvez supprimer des résultats d’historique de recherche individuels de la liste instantanée de la page de recherche Google ainsi que Mon activité Google sur tous les produits de Google sur activity.google.com/myactivity. mon activité google Il est essentiel de sécuriser notre historique de recherche et d’autres activités des autres pour des raisons personnelles.


登录 *


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