【牛客网】创造新世界

2024-09-03 14:08
文章标签 牛客 新世界 创造

本文主要是介绍【牛客网】创造新世界,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

/*******************************************************************

问题描述:

众所周知计算机代码底层计算都是0和1的计算,牛牛知道这点之后就想使用0和1创造一个新世界!牛牛现在手里有n个0和m个1,给出牛牛可以创造的x种物品,每种物品都由一个01串表示。牛牛想知道当前手中的0和1可以最多创造出多少种物品。 

输入描述:
输入数据包括x+1行:第一行包括三个整数x(2 ≤ x ≤ 20),n(0 ≤ n ≤ 500),m(0 ≤ m ≤ 500),以空格分隔接下来的x行,每行一个01串item[i],表示第i个物品。每个物品的长度length(1 ≤ length ≤ 50)
输出描述:
输出一个整数,表示牛牛最多能创造多少种物品
输入例子:
3 3 1
1
00
100
输出例子:
2

********************************************************************/

#include <iostream>
#include <vector>
#include <string.h>
using  namespace std;




//统计  字符串中 0 和 1 的个数
void count(string  s,vector<int> &zeros,vector<int> &ones,int i)
{
    int numOf0 = 0,numOf1 = 0;
    for(int ii=s.size()-1;ii>=0;--ii)
    {
        if(s[ii] =='0')
        {
            ++numOf0;
        }
        else
        {
            ++numOf1;
        }
    }
    zeros[i] = numOf0;
    ones[i] = numOf1;
}
int main()
{
    int x,n,m;
    cin>>x>>n>>m;
    vector<int>  zeros(20,0);
    vector<int>  ones(20,0);
    vector<vector<int>> dp(501,vector<int>(501,0));
    string s;
    for(int ii = 0;ii<x;ii++)
    {
        cin>>s;
        count(s,zeros,ones,ii);
    }
    //动态规划  0-1背包问题
    for(int ii = 0;ii<x;ii++)
        for(int jj = n;jj>=zeros[ii];--jj)
            for(int kk=m;kk>=ones[ii];--kk)
            {
                dp[jj][kk] = max(dp[jj][kk],dp[jj- zeros[ii]][kk - ones[ii]]+1);
            }
    cout<<dp[n][m]<<endl;
}

这篇关于【牛客网】创造新世界的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1133171

相关文章

每日一题|牛客竞赛|四舍五入|字符串+贪心+模拟

每日一题|四舍五入 四舍五入 心有猛虎,细嗅蔷薇。你好朋友,这里是锅巴的C\C++学习笔记,常言道,不积跬步无以至千里,希望有朝一日我们积累的滴水可以击穿顽石。 四舍五入 题目: 牛牛发明了一种新的四舍五入应用于整数,对个位四舍五入,规则如下 12345->12350 12399->12400 输入描述: 输入一个整数n(0<=n<=109 ) 输出描述: 输出一个整数

牛客小白月赛100部分题解

比赛地址:牛客小白月赛100_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛_牛客竞赛OJ A.ACM中的A题 #include<bits/stdc++.h>using namespace std;#define ll long long#define ull = unsigned long longvoid solve() {ll a,b,c;cin>>a>>b>

牛客小白月赛100(A,B,C,D,E,F三元环计数)

比赛链接 官方讲解 这场比较简单,ABC都很签到,D是个不太裸需要预处理的 B F S BFS BFS 搜索,E是调和级数暴力枚举,F是三元环计数。三元环考的比较少,没见过可能会偏难。 A ACM中的A题 思路: 就是枚举每个边变成原来的两倍,然后看看两短边之和是否大于第三边即可。 不能只给最短边乘 2 2 2,比如 1 4 8 这组数据,也不能只给第二短边乘 2 2 2,比

笔试强训,[NOIP2002普及组]过河卒牛客.游游的水果大礼包牛客.买卖股票的最好时机(二)二叉树非递归前序遍历

目录 [NOIP2002普及组]过河卒 牛客.游游的水果大礼包 牛客.买卖股票的最好时机(二) 二叉树非递归前序遍历 [NOIP2002普及组]过河卒 题里面给的提示很有用,那个马的关系,后面就注意,dp需要作为long的类型。 import java.util.Scanner;// 注意类名必须为 Main, 不要有任何 package xxx 信息publ

每日OJ_牛客_求和(递归深搜)

目录 牛客_求和(递归深搜) 解析代码 牛客_求和(递归深搜) 求和_好未来笔试题_牛客网 解析代码         递归中每次累加一个新的数,如果累加和大于等于目标,结束递归。此时如果累加和正好等于目标,则打印组合。向上回退搜索其它组合。此题本身就是一个搜索的过程,找到所有的组合。 #include <iostream>#include <cmath>#in

第一章 MUD:创造世界的巫师

自从有了游戏之后,人们不满足于做屏幕前的操控者,而是梦想着自己能够进入到游戏的绚丽世界中,在剑与魔法的世界中拯救世界,称为吟游诗人歌颂的屠龙 勇者,或者在武侠世界中快意恩仇,体验江湖恩怨儿女情长。网络游戏的出现让这个梦想渐渐变为可以触摸的东西,直至成为现实。   如果要追溯网络游戏的历史,我们要将目光投向20世纪70年代。早在1969年,美国人瑞克•布罗米(Rick Blom

牛客《剑指Offer》 -- 数值的整数次方

题目描述 给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。 思路 特别注意负数的情况,出现负数,将其转化为正数然后求倒数。 class Solution {public:double Power(double base, int exponent) {double total = 1;bool flag = false

牛客网《剑指Offer》 二进制中1的个数

题目描述 输入一个整数,输出该数二进制表示中1的个数。其中负数用补码表示。 思路 负数用补码,其实就是求一个数据在计算机中是存储是怎么样子的。用位运算,就能很好实现。 class Solution {public:int NumberOf1(int n) {int count = 0;int flag = 1;while (flag != 0) {if ((n & f

牛客网《剑指Offer》 矩形覆盖

题目描述 我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形,总共有多少种方法? class Solution {public:int rectCover(int number) {if(number==0) return 0;if(number==1) return 1;if(number==2) return 2;retu

牛客《剑指Offer》 变态跳台阶

题目描述 一只青蛙一次可以跳上1级台阶,也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。 思路 根据 普通的跳台阶可以总结出 f(n) = f(n-1) + f(n-2) +f(n-3) + 。。。。+ f(1) +1 不妨设 f(0) = 1 , 则易得 class Solution {public:int jumpFloorII(int n