ACM-ICPC 2018 焦作赛区网络预赛 K Transport Ship (多重背包)

摘要:
对于每一次询问,找出有多少计划使用这些船来运输货物,并且使用的船必须是满的。乍一看,这是一个背包问题。找到多个背包的解的数量,将数量为m的对象分成log2个对象,然后制作01个背包。只需在此处更改多个背包模板的转移公式。

https://nanti.jisuanke.com/t/31720

题意

t组样例,n种船只,q个询问,接下来n行给你每种船只的信息:v[i]表示这个船只的载重,c[i]表示这种船只有2^(c[i]1)只。

对于每个询问,求用这些船装s的货物的方案数有多少,用到的船必须装满。 

分析

一眼就是背包类的题,多重背包求方案数,将数量为m的物体分为log2(m)种物体,然后做01背包。在这里只需改改多重背包模板的转移式子就好。

背包九讲小总结:https://www.cnblogs.com/fht-litost/p/9204147.html

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e4+10;
const int mod = 1e9 + 7;

ll F[maxn];
int V=10000;
void ZeroOnePack(int C){
    for(int v = V; v>=C ; v--)
        F[v] = (F[v]+F[v-C])%mod;
}
void CompletePack(int C){
    for(int v = C; v<=V ; v++)
        F[v] = (F[v]+F[v-C])%mod;
}
void MultiplePack(int C,int M){
    if( C*M >= V ){
        CompletePack(C);
        return;
    }
    int k = 1;
    while( k < M ){
        ZeroOnePack(k*C);
        M = M - k;
        k <<= 1;
    }
    ZeroOnePack(M*C);
}

int main(){
       int t;
    scanf("%d",&t);
    while(t--){
        int n,q,s,v,c;
        scanf("%d%d",&n,&q);
        memset(F,0,sizeof(F));
        F[0]=1;
        for(int i=1;i<=n;i++){
            scanf("%d%d",&v,&c);
            c=(1<<c)-1;
            MultiplePack(v,c);
        }
        while(q--){
            scanf("%d",&s);
            printf("%lld
",F[s]);
        }
    }
    return 0;
}

免责声明:文章转载自《ACM-ICPC 2018 焦作赛区网络预赛 K Transport Ship (多重背包)》仅用于学习参考。如对内容有疑问,请及时联系本站处理。

上篇ACM-ICPC 2018 焦作赛区网络预赛 L Poor God Water(矩阵快速幂,BM)ACM-ICPC 2018 焦作赛区网络预赛 I Save the Room(水题)下篇

宿迁高防,2C2G15M,22元/月;香港BGP,2C5G5M,25元/月 雨云优惠码:MjYwNzM=

相关文章

hdu 2188 悼念512汶川大地震遇难同胞——选拔志愿者(Bash Game)

题意:从0开始捐款,每次不超过m元,首先达到n元的获胜 思路:等同于从n开始,每次取不超过m,首先达到0的获胜。(Bash Game) #include<iostream>#include<stdio.h> using namespacestd; intmain(){ intc,n,m; scanf("%d",&...

2013 ACMICPC China Nanjing Invitational Programming Contest 总结

A.Play the Dice(HDU 4586) 思路: 很裸的一道概率题,容易得到公式ans=1/n*va[1]+1/n*va[2]+...+1/n*va[n]+m/n*ans,va[i]为对应位置得到的钱数,但是细节不得不注意!!第一次没看到无限多钱要输出inf,第二次没想到,即使n==m也不一定无限多钱,因为有可能每个面得到的钱数都是0. #in...

HDU 1114 Piggy-Bank

题解:完全背包问题(背包要装满) #include <cstdio> using namespacestd; inte,b,n; int f[10005]; int p[505],w[505]; intmain(){ intt; scanf("%d",&t); while(t--...

C语言学生信息管理系统

一、需求分析 学生信息管理系统: 学生信息管理有许多使用功能,使用非常普遍。 需要有的功能是输入、输出、查找、排序、删除和修改等。 用菜单实现,界面功能简洁明了,需要容错,考虑人性化的设计。 二、总体设计 学生包含许多属性,考虑使用结构体来存储。由于不确定学生人数,还有要对信息增加、修改、删除等,使用动态链表实现较为方便。 菜单的设计根据用户的输入来执行不同...

hdu 5066 小球碰撞(物理题)

http://acm.hdu.edu.cn/showproblem.php?pid=5066 中学物理题 #include <cstdio> #include <cstdlib> #include <cmath> #include <cstring> #include <string> #inc...

它们其实都是“图”

二分图判定 问题描述:给定一个具有n个顶点的图,要对图上每个顶点染色,并且要使相邻的顶点颜色不同,问是否能最多用2种颜色进行染色。题目保证没有重边和自环。 限制条件:1≤n≤1000 分析:科普:把相邻点染成不同颜色的问题叫做图着色问题。对图进行染色所需要的最小颜色称为最小着色数。最小着色数是2的图称作二分图。如果只用2种颜色,那么确定一个顶点的颜色之后...