首页 > 其他分享 >P1757 通天之分组背包

P1757 通天之分组背包

时间:2024-03-04 22:56:30浏览次数:31  
标签:通天 int P1757 len 分组 max 1005 dp

原题链接

题解

对于每个容量,当前组 \(i\) 而言,放的决策有 \(size(i)+1\) 种

code

#include<bits/stdc++.h>
using namespace std;
struct unit
{
    int w,v;
};
vector<unit> G[1005];
int main()
{
    int m,n;
    cin>>m>>n;

    int len=0;
    for(int i=1;i<=n;i++)
    {
        int x,y,z;
        cin>>x>>y>>z;
        G[z].push_back({x,y});
        len=max(len,z);
    }


    int dp[1005]={0};
    for(int i=1;i<=len;i++)
    {
        for(int j=m;j>=1;j--)
        {
            for(auto it: G[i])
            {
                int w=it.w,v=it.v;
                if(j>=w) dp[j]=max(dp[j],dp[j-w]+v);
            }
        }
    }

    cout<<dp[m];
    return 0;
}

标签:通天,int,P1757,len,分组,max,1005,dp
From: https://www.cnblogs.com/pure4knowledge/p/18052927

相关文章

  • 如何将流量报文按照协议类型分组?Scapy
    遇到一个困扰了很久的问题:一个pcap文件中包含了各种类型的报文(比如DNP3、DHCP、DNS、TCP、IP、MQTT、MODBUS等等)需要将这个文件中的报文按照协议类型进行分组,将属于同一个协议的报文分在一起。我之前遇到这种情况都是通过wireshark按类型导出就可以了。但是现在这个pcap文件......
  • 49. 字母异位词分组(中)
    目录题目题解:字典题目给你一个字符串数组,请你将字母异位词组合在一起。可以按任意顺序返回结果列表。字母异位词是由重新排列源单词的所有字母得到的一个新单词。示例1:输入:strs=["eat","tea","tan","ate","nat","bat"]输出:[["bat"],["nat","ta......
  • golang中员工分组分页获取的一种方案
    在业务中,有一个场景,A系统需要提供一个接口,返回组织架构信息,供B系统入库,即B系统的组织架构是从A系统中同步过来的。这个场景下存在一个小问题,B系统期望A系统按照组织树层序遍历分页返回。这样B系统就不需要担心新增组织时找不到父级组织了。那么A系统要怎么做呢?方案1:在数据库......
  • react 使用splitChunks 拆分组件,缩小项目体积,加快加载访问速度
    react编写项目引入npm包打包时,总会将一些npm包重复打包的不同的js文件中,可以使用splitChunks进行拆分,降低体积,加快速度1、安装npminstallcustomize-crawebpack-bundle-analyzer2、修改启动命令,在package.json中修改"scripts":{"start":"react-app-rewiredstar......
  • JavaScript 实现JSON 对象数组以某个属性进行分组处理
    JavaScript实现JSON对象数组以某个属性进行分组处理要在JavaScript中对JSON对象数组的某个属性进行分组处理,你可以使用一个对象来存储分组后的结果。下面是一个简单的示例,演示了如何对JSON对象数组中的某个属性进行分组处理:假设我们有一个JSON对象数组,每个对象都有ca......
  • 洛谷题单指南-贪心-P4447 [AHOI2018初中组] 分组
    原题链接:https://www.luogu.com.cn/problem/P4447题意解读:将一个有序的数列,按不重复连续数分成一组,可分成若干组,使得人数最少的组在各种分组方式之中是最大的。解题思路:观察样例说明,有6个测试点的ai​互不相同,因此直接将数据排序,然后连续数分成一组,计算每组数量最少的,即为答案,6......
  • Power BI - 如何对发布的报告进行分组
    故事背景:用户在PowerBI发布报告后,页导航中的报告一般是不分组的(如图红色矩形框内容).如何才能在页导航中,将报告进行分组(如图红色矩形框内容)?方便查看报告用户在前端看报告的时候会更有逻辑性,条理性。 解决方案:解决方案需要通过创建PowerBIAppreport来实现。 ......
  • 洛谷题单指南-贪心-P1094 [NOIP2007 普及组] 纪念品分组
    原题链接:https://www.luogu.com.cn/problem/P1094题意解读:贪心选择解题思路:贪心策略:将纪念品按价格由小到大排序,优先选择价格大的一直到超过分组价格上限,再选择价格小的直到超过价格上限,此为一组重复以上过程,直到所有数据都遍历到,采用一头一尾双指针即可。证明:如果最大价格......
  • MySQL——分组查询
    MySQL——分组查询在实际应用中,可能会有需要先进行分组,再对每一组的数据进行操作的需求吗,这个时候我们需要进行分组查询。分组语句结构:select分组函数(字段),参加分组的字段from表名groupby参加分组的字段;执行语句的顺序:from->where->groupby->select->orderby......
  • JavaScript 的新数组分组方法
    对数组中的项目进行分组,你可能已经做过很多次了。每次都会手动编写一个分组函数,或者使用lodash的groupBy函数。好消息是,JavaScript现在有了分组方法,所以你再也不必这样做了。Object.groupBy和Map.groupBy这两个新方法将使分组变得更简单,并节省我们的时间或依赖性。以前......