称砝码（C++牛客网）

痛定思痛。 2022-11-11 05:12 207阅读 0赞

解题思路：

（1）动态规划，dp\[n\]=去重（dp\[n-1\]+\{dp\}+v\[n\]）

#include<iostream>
    #include<vector>
    #include<iostream>
    #include<unordered_map>
    using namespace std;
    
    int helper(vector<int> &weight,vector<int> &num) {
        vector<int> v;
        for(int i=0;i<num.size();i++) {
            for(int j=0;j<num[i];j++) {
                v.push_back(weight[i]);
            }
        }
        unordered_map<int,int> mp;
        mp[0]=0;
        for(int i=0;i<v.size();i++) {
            vector<int> vec;
            for(auto it=mp.begin();it!=mp.end();it++) {
                vec.push_back(it->first+v[i]);
            }
            for(int j=0;j<vec.size();j++) {
                mp[vec[j]]=0;
            }
        }
        return mp.size();
    }
    
    int main() {
        int n,a;
        while(cin>>n) {
            vector<int> weight,num;
            for(int i=0;i<n;i++) {
                cin>>a;
                weight.push_back(a);
            }
            
            for(int i=0;i<n;i++) {
                cin>>a;
                num.push_back(a);
            }
            cout<<helper(weight,num)<<endl;
        }
        return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，207人围观）

还没有评论，来说两句吧...

相关阅读

相关 HJ41 称砝码

> [牛客华为机试题库【题号 HJ开头】（重点看）][HJ] > [牛客在线编程算法篇【题号NC开头】][NC] > [剑指offer【题号 JZ开头】][offer_

Love The Way You Lie/ 2024年03月27日 13:56/ 0 赞/ 82 阅读

相关华为OD机试 C++ 称砝码

题目你有一些不同的砝码，每个砝码都有自己的重量和数量。试问，用这些砝码，你可以得到多少种不同的重量组合？输入：第一行给出砝码的种类数 n (1 ≤ n ≤ 10

迈不过友情╰/ 2023年10月15日 09:52/ 0 赞/ 8 阅读

相关 AcWing——砝码称重

[4942. 砝码称重 - AcWing题库][4942. _ - AcWing] 1、题目给定一个天平和 101 个砝码。 101 个砝码的重量依次为 n⁰,n¹

比眉伴天荒/ 2023年09月27日 18:16/ 0 赞/ 121 阅读

相关砝码称重

题目：有一个天平，有六种砝码，分别重1,2,3,5,10,20克，每种砝码各有5,3,2,2,1,1个，计算天平能称出的重量及种类方法一： include <

Love The Way You Lie/ 2023年07月17日 15:35/ 0 赞/ 14 阅读

相关等差数列（C++牛客网）

解题思路：（1）数学思想 include<iostream> using namespace std; int helper(

女爷i/ 2022年11月13日 10:29/ 0 赞/ 202 阅读

相关称砝码（C++牛客网）

解题思路：（1）动态规划，dp\[n\]=去重（dp\[n-1\]+\{dp\}+v\[n\]） include<iostream> include<ve

痛定思痛。/ 2022年11月11日 05:12/ 0 赞/ 208 阅读

相关华为OJ称砝码

问题描述：现有一组砝码，重量互不相等，分别为m1、m2……mn；他们可取的最大数量分别为x1、x2……xn。现在要用这些砝码去称物体的重量，问能称出多少中不同的重量

分手后的思念是犯贱/ 2022年10月01日 00:48/ 0 赞/ 214 阅读

相关称砝码问题

题目描述有一组砝码，重量互不相等，分别为 m1 、 m2 、 m3……mn ；它们可取的最大数量分别为 x1 、 x2 、 x3……xn 。现要用这些砝码去称

一时失言乱红尘/ 2022年08月08日 05:15/ 0 赞/ 205 阅读

相关 [编程题]称砝码

> Talk is cheap, show me the code. 一、问题描述现有一组砝码，重量互不相等，分别为m1,m2,m3…mn；每种砝码对应的

太过爱你忘了你带给我的痛/ 2022年07月13日 03:21/ 0 赞/ 206 阅读

相关【牛客网】C/C++牛客网专项刷题（04）

以下为牛客网C/C++专项刷题： 1、有以下程序： include <stdio.h> include <string.h> voi

青旅半醒/ 2022年05月18日 04:49/ 0 赞/ 3273 阅读