hdu5616 暴力枚举

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 = ;

int w[maxn];

bool vis1[maxn];

bool vis2[maxn];

int N;

int main()

{

    int cas;

    cin >> cas;

    while(cas--)

    {

        cin >> N;

        for(int i =  ; i < N ; i++)

        {

            cin >> w[i];

        }

        memset(vis1,,sizeof(vis1));

        memset(vis2,,sizeof(vis2));

        vis1[] = ;

        for(int i =  ; i < N ; i++)

        {

            for(int j =  ; j <=  ; j++)//顶多20 * 100 个

            {

                  //这里是j不是i

                if(vis1[j] != )  //如果已经有元素存在，那么在新地砝码加到左边，加到右边或者不加，分三种情况

                {

                    vis2[j] = true;

                    vis2[abs(j - w[i])] = true;

                    vis2[j + w[i]] = true;

                }

            }

            for(int k =  ; k <=  ; k++) //将vis2清空

            {

                vis1[k] = vis2[k];

                vis2[k] = ;

            }

        }

        int m;

        cin >> m;

        long long int tmp;

        for(int i =  ; i < m ; i++)

        {

            cin >> tmp;

            if(vis1[tmp] ==  || tmp <  || tmp > )

            {

                cout << "NO" << endl;

            }

            else

            {

                cout << "YES" << endl;

            }

        }

    }

    return ;

}

巴特西

hdu5616 暴力枚举

最新文章

热门文章