首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >【HDU】5616 - Jam's balance(母函数变型)

【HDU】5616 - Jam's balance(母函数变型)

作者头像
FishWang
发布2025-08-27 08:57:09
发布2025-08-27 08:57:09
7500
代码可运行
举报
运行总次数:0
代码可运行

点击打开题目

Jam's balance

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 1133 Accepted Submission(s): 531

Problem Description

Jim has a balance and N weights. The balance can only tell whether things on different side are the same weight. Weights can be put on left side or right side arbitrarily. Please tell whether the balance can measure an object of weight M.

Input

The first line is a integer , means T test cases. For each test case : The first line is , means the number of weights. The second line are number, i'th number means the i'th weight's weight is . The third line is a number . is the weight of the object being measured.

Output

You should output the "YES"or"NO".

Sample Input

代码语言:javascript
代码运行次数:0
运行
复制
   1
2
1 4
3
2
4
5

Sample Output

代码语言:javascript
代码运行次数:0
运行
复制
   NO
YES
YES


   
    
     Hint
    
For the Case 1:Put the 4 weight alone
For the Case 2:Put the 4 weight and 1 weight on both side

Source

BestCoder Round #70

同样是母函数,但是砝码可以放到两边,计数的时候算一下 abs( j - k ) 就行了。

代码如下:

代码语言:javascript
代码运行次数:0
运行
复制
#include <cstdio>
#include <cstring>
int c[2000+11];
int t[2000+11];
int sum;
int abs(int x)
{
	return x < 0 ? -x : x;
}
void init()
{
	sum = 0;
	memset (c,0,sizeof (c));
	memset (t,0,sizeof (t));
}
int main()
{
	int u;
	int w[22];
	int n,q;
	scanf ("%d",&u);
	while (u--)
	{
		scanf ("%d",&n);
		init();		//初始化 
		for (int i = 1 ; i <= n ; i++)
		{
			scanf ("%d",&w[i]);
			sum += w[i];
		}
		c[w[1]] = c[0] = 1;
		for (int i = 2 ; i <= n ; i++)
		{
			for (int j = 0 ; j <= sum ; j++)
				for (int k = 0 ; k <= w[i] && k+j <= sum ; k += w[i])
				{
					t[k+j] += c[j];
					t[abs(k-j)] += c[j];		//砝码放到另一个盘子上 
				}
			for (int j = 0 ; j <= sum ; j++)
			{
				c[j] = t[j];
				t[j] = 0;
			}
		}
		scanf ("%d",&q);
		while (q--)
		{
			int x;
			scanf ("%d",&x);
			printf (c[x] ? "YES\n" : "NO\n");
		}
	}
	return 0;
}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2025-08-26,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • Jam's balance
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档