首页 > 代码库 > J - 砝码称重 改自51nod1449
J - 砝码称重 改自51nod1449
J - 砝码称重
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 128000/64000 KB (Java/Others)
Submit Status
Problem Description
有一个物品和一些已知质量的砝码和天平，问能不能用这些砝码称出这个物品的重量（天平两边都可以放砝码）
Input
多样例输入，样例数<=20000
对于每个样例：
第一行输入两个数n，m，表示砝码数量和重物质量,1 ≤ m ≤ 1018
第二行输入n个数a1 ,a2 , ... ,an ,1018 ≥ ai+1 ≥ 3 * ai ≥ 1
Output
Case x: y
x代表第几个样例，若能称出重物的质量，y为YES，否则y为NO
Sample Input
3 71 3 9
Sample Output
Case 1: YES
Hint
样例为一边盘放重物和质量为3的砝码，另一边盘放质量为1和9的砝码
1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef long long LL; 4 const int N=1e5+10; 5 const int INF=0x3f3f3f3f; 6 int cas=1,T; 7 int n,vis[40]; 8 LL a[40],b[40],m; 9 bool dfs(int x,LL sum,int v)10 {11 if(sum==0) return 1;12 if(x<0 || b[x]<sum || sum<0) return 0;13 if(!vis[x])14 {15 vis[x]=v;16 if(dfs(x-1,sum-a[x],v)) return 1;17 vis[x]=0;18 }19 if(dfs(x-1,sum,v)) return 1;20 return 0;21 }22 bool solve(LL sum,int v)23 {24 if(sum<0) return 0;25 int id=0;26 while(a[id]<=sum) id++;27 if(dfs(id-1,sum,v)) return 1;28 if(!vis[id-1])29 {30 vis[id-1]=v;31 if(solve(sum-a[id-1],v)) return 1;32 vis[id-1]=0;33 }34 if(!vis[id])35 {36 vis[id]=v;37 if(solve(a[id]-sum,v^1)) return 1;38 vis[id]=0;39 }40 return 0;41 }42 int main()43 {44 // freopen("1.in","w",stdout);45 freopen("1.in","r",stdin);46 freopen("1.out","w",stdout);47 // scanf("%d",&T);48 while(scanf("%d%lld",&n,&m)==2)49 {50 memset(vis,0,sizeof(vis));51 a[0]=b[0]=0;52 for(int i=1;i<=n;i++)53 {54 scanf("%lld",a+i);55 b[i]=b[i-1]+a[i];56 }57 a[n+1]=1LL*INF*INF;58 b[n+1]=b[n]+a[n+1];59 vis[0]=vis[n+1]=1;60 printf("Case %d: ",cas++);61 if(solve(m,2))62 {63 int sum1=0,sum2=0;64 puts("YES");65 /*for(int i=1;i<=n;i++) if(vis[i]==2) printf("%d ",a[i]),sum1+=a[i];66 printf("\n");67 for(int i=1;i<=n;i++) if(vis[i]==3) printf("%d ",a[i]),sum2+=a[i];68 printf("\n");69 printf("sum1:%d sum2:%d m:%d dif:%d\n",sum1,sum2,w,sum1-sum2);*/70 }71 else puts("NO");72 }73 // printf("%d %d\n",clock(),CLOCKS_PER_SEC);74 // printf("time=%.3f\n",(double)clock()/CLOCKS_PER_SEC);75 return 0;76 }
1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef unsigned long long ULL; 4 typedef long long LL; 5 const int INF = 0x3f3f3f3f; 6 const double eps = 1e-9; 7 long long a[40]; 8 int vis[40]; 9 int cas=1;10 int check(int n, LL x, LL p)11 {12 for(int i=n-1;i>=0;--i)13 {14 if(x - a[i] >= p) x -= a[i], vis[i] = 0;15 if(x >= p + a[i]) p += a[i], vis[i] = 2;16 }17 if(x == p) return 1;18 else return 0;19 }20 21 int main()22 {23 // freopen("1.in","r",stdin);24 // freopen("t1.out","w",stdout);25 int T, cas=1;26 int n;27 LL m;28 while(scanf("%d%lld", &n, &m) == 2)29 {30 for(int i=0;i<n;++i)31 scanf("%lld", &a[i]);32 sort(a, a+n);33 int flag = 0;34 long long sum = m;35 for(int i=0;i<n&&!flag;++i)36 {37 memset(vis, 0, sizeof vis);38 for(int j=0;j<i;++j) vis[j] = 1;39 vis[i] = 2;40 if(sum == a[i])41 flag = 1;42 else43 {44 flag = check(i, sum, a[i]);45 if(!flag)46 {47 memset(vis, 0, sizeof vis);48 for(int j=0;j<i;++j) vis[j] = 1;49 flag = check(i, sum, 0);50 }51 sum += a[i];52 }53 }54 printf("Case %d: ",cas++);55 puts(flag?"YES":"NO");56 /* if(flag)57 {58 LL sum = m;59 for(int i=0;i<n;++i) if(vis[i] == 1) printf("%lld ", a[i]), sum += a[i]; puts("");60 printf("lsum:%lld\n", sum);61 sum = 0;62 for(int i=0;i<n;++i) if(vis[i] == 2) printf("%lld ", a[i]), sum += a[i]; puts("");63 printf("rsum:%lld\n", sum);64 }*/65 }66 67 // printf("time=%.3lf\n",(double)clock()/CLOCKS_PER_SEC);68 return 0;69 }
题解：
由砝码质量的上限可知n只有几十。
若a[i]刚好大于m，则不会用到a[i+1],
因为a[1]+a[2]+...+a[i]+m < a[i+1]/2+m <= a[i+1]/2+a[i+1]/3 < a[i+1]
递归执行以下过程
1.每次搜索比m小的a[i]能否凑成m
2.若不可以凑成，则m=a[i]-m,回到1
3.若2还是不可以凑成，则m=m-a[i-1],回到1
搜索能否凑成a[i]时记得剪枝
J - 砝码称重 改自51nod1449
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。