专栏首页个人学习总结做题总结——小M和天平

做题总结——小M和天平

做题总结——小M和天平

题目

题意分析:

根据这道题给出的数据范围可以知道,利用所有的石头能够查询的物体质量是不会查过100*100=10000的,所以可以直接利用暴力枚举的方法进行求解。

做题思路: 利用一个二维数组dp[i] [j],其中i表示前i个石头,j表示物体质量,如果利用前i个石头能够称出质量为j的物体,则dp[i][j]标记为1,否则为0。如果dp[i-1][j]=1,则可以得出三个结论:dp[i][j]一定等于1、dp[i][j+w[i]]一定等于1、dp[i][abs(j-w[i])]一定等于1(w[i]是第i个石头的质量),所以只需要对i、j进行枚举即可解决。

代码实现

#include<bits/stdc++.h>
using namespace std;
int dp[102][10002];
int main()
{
    int n,m,data;
    while(cin>>n)
    {
        int i,j,w[102];
        memset(w,0,sizeof(w));
        memset(dp,0,sizeof(dp));
        for(i=1;i<=n;i++)
        {
            cin>>w[i];
        }
        dp[0][0]=1;
        for(i=1;i<=n;i++)
        {
            for(j=0;j<=10000;j++)
            {
                if(dp[i-1][j])    //这里是整道题目的关键
                {
                    dp[i][j]=1;
                    dp[i][j+w[i]]=1;
                    dp[i][abs(j-w[i])]=1;
                }
            }
        }
        cin>>m;
        while(m--)
        {
            cin>>data;
            if(data<=10000 && dp[n][data])    //如果n块石头能够称出质量为data的物体,并且物体质量<=10000
            {
                cout<<"YES"<<endl;
            }
            else
            {
                cout<<"NO"<<endl;
            }
        }
    }
    return 0;
}

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

我来说两句

0 条评论
登录 后参与评论

相关文章

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

    小M和天平 Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Ja...

    ShenduCC
  • 打卡群刷题总结0718——最小路径和

    链接:https://leetcode-cn.com/problems/minimum-path-sum

    木又AI帮
  • 大数据计数原理1+0=1这你都不会算No.77

    完结篇。 这个系列写到这里算是结束了,真是不容易说实话,查了好多好多的资料,真的很难相信懒得要命的我能写完这个系列 T_T。有兴趣的小伙伴可以在菜单看看整个系列...

    企鹅号小编
  • 2000 楼房重建 2012年

     时间限制: 1 s  空间限制: 256000 KB  题目等级 : 大师 Master 题解  查看运行结果 题目描述 Description   小A的楼...

    attack
  • 打卡群刷题总结0816——三角形最小路径和

    链接:https://leetcode-cn.com/problems/triangle

    木又AI帮
  • Coursera吴恩达《优化深度神经网络》课程笔记(2)-- 优化算法

    上节课我们主要介绍了如何建立一个实用的深度学习神经网络。包括Train/Dev/Test sets的比例选择,Bias和Variance的概念和区别:Bias对...

    红色石头
  • Python3经典100例(①)

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

    村雨遥
  • 动态规划该如何优化?我总结了这些套路,以后优化就是分分钟

    前两天写一篇长达 8000 字的关于动态规划的文章告别动态规划,连刷40道动规算法题,我总结了动规的套路

    帅地
  • SAP成都研究院CEC团队三巨头之一:M君的文章预告

    国人总倾向于把特点或者作用类似的人或物放在一起比较并做出排名,于是就有了许多“某某某三巨头”的称谓。

    Jerry Wang
  • 对话机器人ChatBot综述

    网址:http://www.tuling123.com/ 特点:提供场景服务

    birdskyws
  • 最近的几个技术问题总结和答疑 (r8笔记第19天)

    笔记写了不少,有时候有的朋友问我几个关键字,我就会从脑海里进行搜索,凡是写过的,搜索一下总能找到,帮助了别人,提高了自己,何乐而不为。 但是笔记写了很多...

    jeanron100
  • 【动态规划/路径问题】进阶「最小路径和」问题 ...

    给定一个包含非负整数的 m x n 网格 grid ,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。

    宫水三叶的刷题日记
  • SAP成都研究院CEC团队三巨头之一:M君的文章预告

    国人总倾向于把特点或者作用类似的人或物放在一起比较并做出排名,于是就有了许多“某某某三巨头”的称谓。

    Jerry Wang
  • 不到70行Python代码,轻松玩转RFM用户分析模型(附案例数据和代码)

    本文从RFM模型概念入手,结合实际案例,详解Python实现模型的每一步操作,并提供案例同款源数据,以供同学们知行合一。

    数据森麟
  • 不到70行Python代码,轻松玩转RFM用户分析模型(附案例数据和代码)

    本文从RFM模型概念入手,结合实际案例,详解Python实现模型的每一步操作,并提供案例同款源数据,以供同学们知行合一。

    CDA数据分析师
  • 不到70行Python代码,轻松玩转RFM用户分析模型(附案例数据和代码)

    本文从RFM模型概念入手,结合实际案例,详解Python实现模型的每一步操作,并提供案例同款源数据,以供同学们知行合一。

    木东居士
  • 不到70行Python代码,轻松玩转RFM用户分析模型(附案例数据和代码)

    本文从RFM模型概念入手,结合实际案例,详解Python实现模型的每一步操作,并提供案例同款源数据,以供同学们知行合一。

    张俊红
  • 我是如何得知10W+的访问量多来自工作日的 | 塔秘

    导读:有位朋友分析了一下每天某个时间发文章的访问量区别,以讨论非系统性因素对文章访问量的影响。之所以进一步讨论工作日和周末发文对文章访问量的影响,一是觉得很有...

    灯塔大数据
  • 业界 | Facebook Messenger 平台 2.0,有哪些聊天机器人的新玩法?

    AI科技评论消息:在昨晚的 F8 开发者大会上, Facebook Messenger 事业部副总裁 David Marcus,宣布了新一代 Messenger...

    AI科技评论

扫码关注云+社区

领取腾讯云代金券