2018焦作区域赛预选赛K: Transport Ship(0-1背包)_2018 区域赛焦作 k_125小黑黑521的博客-程序员秘密

技术标签: dp专题  

传送门

把数量用二进制展开,比如2的3次-1,就可以拆成1个2个和4个,就能够代表所有的容量了,这样的话最多只有20*20一共400个包,做一次01背包即可,非常方便的想法。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod = 1e9+7;
int dp[500][10005],wei[1005],n,q,num;
signed main()
{
    int T;
    scanf("%lld",&T);
    while(T--)
    {
        num = 0;
        scanf("%lld%lld",&n,&q);
        for(int i = 1;i <= n; i++)
        {
            int c,w;
            scanf("%lld%lld",&w, &c);
            int tmp = 1;
            while(c--)
            {
                wei[++num] = tmp * w;
                tmp <<= 1;
            }
        }
        dp[0][0] = 1;
        for(int i = 1;i <= num; i++)
        {
            for(int j = 0;j <= 10000; j++)
            {
                if(j < wei[i])
                    dp[i][j] = dp[i-1][j];
                else
                    dp[i][j] = (dp[i-1][j] + dp[i-1][j-wei[i]]) % mod;
            }
        }
        while(q--)
        {
            int s;
            scanf("%lld",&s);
            printf("%lld\n",dp[num][s]);
        }
    }
    return 0;
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/xiao__hei__hei/article/details/98316734

智能推荐

jenkins 执行构建 并查看结果_jenkins 测试结果_微风--轻许--的博客-程序员秘密

继完成构建项目配置http://www.cnblogs.com/yajing-zh/p/5111060.html后,则要执行构建。回到jenkins主页之后,我们看到一个新建的项目显示出来:点击进入项目,点击立即构建,之后可看到构建状态条,点击改状态条,进入详情页面,点击Console Output,查看构建log:此时看到git报错,这可能是我git没有配置好,假如是配...

确定缺少驱动的网卡_weixin_33775582的博客-程序员秘密

--检查有几个pci网卡[[email protected] ~]# lspci |grep Ethernet04:00.0 Ethernet controller: Broadcom Corporation NetXtreme II BCM5709 Gigabit Ethernet (rev 20)04:00.1 Ethernet controller: Broadcom Corporation NetXtre...

pandas.Series.plot_冉威的博客-程序员秘密

函数原型Series.plot(kind='line', ax=None, figsize=None, use_index=True, title=None, grid=None, legend=False, style=None, logx=False, logy=False, loglog=False, xticks=None, yticks=None, xlim=None, ylim...

四川2021高考体考成绩查询,2021年四川体育类专业成绩查询时间及入口_中职中专网..._顾凯之的博客-程序员秘密

2020年四川体育类专业考试集中在成都体育学院进行,总分满分为100分,5月9日至10日可领取专业考试成绩通知单。四川省普通高校体育类招生专业考试将按照统一设置考点,统一评分标准,统一考试计分的原则组织实施。报考省内外普通高校体育类专业(只报考单独招生的运动训练及武术与民族传统体育专业除外)的考生,均须参加我省统一组织的体育专业考试。四川省普通高校体育类专业考试考生成绩由省教育考试院传送到各市州招...

java 的初步认识_vbarry215的博客-程序员秘密

Java的初步认识 Java与C++的区别Java中没有指针、结构和类型定义的概念,不再有全局变量,也没有#include和#define等预处理器,也没有多重继承的机制。不仅如此,程序员不用自己释放占用的内存空间,java具有自己的垃圾回收机制。Java支持多线程,而C++不支持。多线程就是同一个时刻同时做多件事情 Java可以跨平台使用Java编译器将java程序编译成

图像分割的应用matlab,基于MATLAB的图像分割方法及应用.doc_weixin_39799307的博客-程序员秘密

PAGEPAGE 24本科毕业设计(论文)课题名称 基于MATLAB的图像分割方法及应用电子信息工程 学院 电子科学与技术 专业学 号学生姓名指导教师起讫日期工作地点摘 要图像处理是一种新兴学科,在短短几十年中得以迅速发展并广泛应用于航天、军事、医学等领域。它是如今信息社会引人注目的多媒体技术中重要组成部分只一。图像分割技术是非常重要的图像处理技术之一,无语是在理论研究还是在实际应用...

随便推点

关于stm32IIC通信协议的简单总结(小白总结文系列二)_RabbitChenc的博客-程序员秘密

IIC通信协议详解IIC(Inter-Integrated CircuitBUS) 集成电路总线。1,物理层:设备之间连接方式IIC的物理特性:1)IIC通信在控制上是一主多从的模式。2)IIC由sda/scl两条通信线构成。scl是串行时钟线,用来控制通讯的时钟频率实现数据收发同步;sda是双向串行数据线,用来控制协议中数据的传输。3) 总线上拉电阻接到电...

Tests run: 2, Failures: 0, Errors: 1, Skipped: 0, Time elapsed: 1.64 s <<< FAILURE! - in com.springt_爱喝怡宝的男孩的博客-程序员秘密

Tests run: 2, Failures: 0, Errors: 1, Skipped: 0, Time elapsed: 1.64 s &lt;&lt;&lt; FAILURE! - in com.springtest.QiniuTest当我打包时,出现了test模块打包不了,这个时候可以这样解决,首先先clean,之后再点击这样打包就可以跳过test了,错误解决...

Button selector使用_Dadaist_的博客-程序员秘密

先写一个xml文件,&lt;?xml version="1.0" encoding="utf-8"?&gt;&lt;selector xmlns:android="http://schemas.android.com/apk/res/android"&gt; &lt;item android:state_activated="true" &gt; &lt;shape android:shape="rectangle"&gt; &lt;corners android:radius=

JavaSwing_8.1:焦点事件及其监听器 - FocusEvent、FocusListener_addfocuslistener_JavaEdge.的博客-程序员秘密

0 FocusEvent低级别事件指示Component已获得或失去输入焦点。 由组件生成此低级别事件(如一个TextField)。 该事件被传递给每一个FocusListener或FocusAdapter注册,以接收使用组件的此类事件对象addFocusListener方法。 ( FocusAdapter对象实现FocusListener接口。)每个此类侦听器对象获取此FocusEvent当事件发生时。有两个焦点事件级别:持久性和暂时性的。 永久焦点改变事件发生时焦点直接移动从一个组件到另一个,例如通

波峰波谷(凸点凹点)的检测算法_波峰波谷算法_三维机器人引导的博客-程序员秘密

如何完成一个三维引导项目:第二步 位姿转化主要使用算子:*对点应用任意仿射3D变换affine_trans_point_3d *创建一个3D姿势create_pose*将齐次变换矩阵转换为三维姿态hom_mat3d_to_pose*将三维姿态转换为齐次变换矩阵pose_to_hom_mat3d*三维姿态求逆pose_invert *姿态相乘,类似矩阵相乘pose_compose *转化一种位姿表示形式convert_pose_type目录如何完成一个三维引导项目:第二步

推荐文章

热门文章

相关标签