专栏首页算法修养浙江工业大学校赛 小M和天平

浙江工业大学校赛 小M和天平

小M和天平

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 568    Accepted Submission(s): 108

Problem Description

小M想知道某件物品的重量,但是摆在他面前的只有一个天平(没有游标)和一堆石子,石子可以放左边也可以放右边。他现在知道每个石子的重量。问能不能根据上述条件,能不能测出所问的重量。

Input

第一行T(1≤T≤100),表示T组数据。 接下来T组数据: 接下来第一行一个数N,表示石子个数。(1≤N≤100) 接下来第二行N个数,表示石子的重量。(1≤w_i≤100) 接下来第三行一个数M,表示询问个数。(1≤M≤100) 接下来M行每行一个数k,表示一个询问。

Output

对于每组数据,输出"YES"或者"NO"

Sample Input

1
2
1  4
3
2
4
5

Sample Output

NO
YES
YES动态规划#include <iostream>
#include <string.h>
#include <math.h>
#include <stdio.h>
#include <algorithm>
#include <stdlib.h>

using namespace std;
typedef long long int LL;
const int maxn=1e5;
int w[105];
int n;
int m;
int dp[10005][105];
int ans[10005];
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        int sum=0;
        int cnt=1;
        memset(dp,0,sizeof(dp));
        memset(ans,0,sizeof(ans));
        for(int i=0;i<=100;i++)
            dp[0][i]=1;
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&w[i]);
            sum+=w[i];
        }
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=sum;j++)
            {
                if(dp[j][i-1]==1)
                    dp[j][i]=1;
                if(w[i]-j>=0&&dp[w[i]-j][i-1]==1)
                    dp[j][i]=1;
                if(j-w[i]>=0&&dp[j-w[i]][i-1]==1)
                {
                    dp[j][i]=1;
                    if(j-2*w[i]>0)
                        dp[j-2*w[i]][i]=1;
                }

            }
        }
        for(int i=1;i<=sum;i++)
        {
            for(int j=1;j<=n;j++)
            {
                
                if(dp[i][j]==1)
                {
                    ans[i]=1;
                    
                    break;
                }
            }
            
            
        }
        scanf("%d",&m);
        int k;
        for(int i=1;i<=m;i++)
        {
            scanf("%d",&k);
            if(k>sum)
            {
                printf("NO\n");
                continue;
            }
            if(k==0)
            {
                printf("YES\n");
                continue;
            }
            if(ans[k]==1)
                printf("YES\n");
            else
                printf("NO\n");
        }

    }
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • HDU-4539郑厂长系列故事——排兵布阵(状态压缩,动态规划)

    郑厂长系列故事——排兵布阵 Time Limit : 10000/5000ms (Java/Other) Memory Limit : 65535/3276...

    ShenduCC
  • HOJ-2662Pieces Assignment(状态压缩,动态规划)

    Pieces Assignment Source : zhouguyue Time limit : 1 sec Memory limit : ...

    ShenduCC
  • LeetCode 221. Maximal Square(DP)

    ShenduCC
  • 状态压缩DP(大佬写的很好,转来看)

    奉上大佬博客 https://blog.csdn.net/accry/article/details/6607703 动态规划本来就很抽象,状态的设定和状态的...

    风骨散人Chiam
  • HOJ-2662Pieces Assignment(状态压缩,动态规划)

    Pieces Assignment Source : zhouguyue Time limit : 1 sec Memory limit : ...

    ShenduCC
  • 【CodeForces 567F】Mausoleum

    1到n每个数字有两个,排成先不降后不升的序列,比如112332,并且满足k个形如 3 <= 6 代表第三个数字要≤第六个数字这样的约束要求,求有多少种排法。

    饶文津
  • 几道暑期实习笔试题

    DFS 回溯法,先判断组成三连对和组成顺子需要的次数,递归深度 k 就是次数。对于对子和单张的可以直接通过枚举数需要打多少次。可以在组成三连对和顺子的时候增加剪...

    echobingo
  • LeetCode 221. Maximal Square(DP)

    ShenduCC
  • P2668 斗地主 dp+深搜版

    题目描述 牛牛最近迷上了一种叫斗地主的扑克游戏。斗地主是一种使用黑桃、红心、梅花、方片的A到K加上大小王的共54张牌来进行的扑克牌游戏。在斗地主中,牌的大小关系...

    attack
  • Day1下午解题报告

    预计分数:0+30+30=60 实际分数:0+30+40=70 T1水题(water) 贪心,按长度排序, 对于第一幅牌里面的,在第二个里面,找一个长度小于,高...

    attack

扫码关注云+社区

领取腾讯云代金券