mes 清空 iter 三种 行处理 -- main clu
2017-08-25 20:08:54
writer:pprp
题目简述:
HDU 5616
? n 个砝码,可以放在天平左右两侧或不放
? m 次询问,每次询问是否可以测出给定重量
? 1 ≤ n ≤ 20
? 1 ≤ m ≤ 100
这道题采用枚举的思路的话实现起来还是有点困难的,
要实现的功能是对每个砝码进行处理,加到左边, 加到右边,或者是不加
看了大神的代码,感觉很巧妙,
设置了两个标记数组
vis1[2005], vis2[2005]
一个 vis1 用来记录当前已经可以实现的重量
另一个 vis2 用来作为中间量,记录处理之后的值
通过这个给我一个处理想这样的题的一个思路吧
代码如下:
- /*
- theme:hdu5616
- writer:pprp
- declare:暴力枚举
- date:2017/8/25
- */
- #include <bits/stdc++.h>
- using namespace std;
- const int maxn = 2005;
- int w[maxn];
- bool vis1[maxn];
- bool vis2[maxn];
- int N;
- int main()
- {
- int cas;
- cin >> cas;
- while(cas--)
- {
- cin >> N;
- for(int i = 0 ; i < N ; i++)
- {
- cin >> w[i];
- }
- memset(vis1,0,sizeof(vis1));
- memset(vis2,0,sizeof(vis2));
- vis1[0] = 1;
- for(int i = 0 ; i < N ; i++)
- {
- for(int j = 0 ; j <= 2000 ; j++)//顶多20 * 100 个
- {
- //这里是j不是i
- if(vis1[j] != 0) //如果已经有元素存在,那么在新地砝码加到左边,加到右边或者不加,分三种情况
- {
- vis2[j] = true;
- vis2[abs(j - w[i])] = true;
- vis2[j + w[i]] = true;
- }
- }
- for(int k = 0 ; k <= 2000 ; k++) //将vis2清空
- {
- vis1[k] = vis2[k];
- vis2[k] = 0;
- }
- }
- int m;
- cin >> m;
- long long int tmp;
- for(int i = 0 ; i < m ; i++)
- {
- cin >> tmp;
- if(vis1[tmp] == 0 || tmp < 0 || tmp > 2000)
- {
- cout << "NO" << endl;
- }
- else
- {
- cout << "YES" << endl;
- }
- }
- }
- return 0;
- }
hdu5616 暴力枚举
来源: http://www.bubuko.com/infodetail-2278600.html