焦作网络赛K-Transport Ship【dp】-白红宇

焦作网络赛K-Transport Ship【dp】

阅读量：4965 次

发布时间：2019-06-12

本文共 2676 字，大约阅读时间需要 8 分钟。

There are $i^{th}ith kind of ship can carry the weight of V[i]V[i] and the number of the i^{th}ith kind of ship is 2^{C[i]} - 12C[i]−1. How many different schemes there are if you want to use these ships to transport cargo with a total weight of SS?$

It is required that each ship must be full-filled. Two schemes are considered to be the same if they use the same kinds of ships and the same number for each kind.

Input

The first line contains an integer $\le T \le 20)T(1≤T≤20), which is the number of test cases.$

For each test case:

The first line contains two integers: $\le N \le 20), Q(1 \le Q \le 10000)N(1≤N≤20),Q(1≤Q≤10000), representing the number of kinds of ships and the number of queries.$

For the next $\le V[i] \le 20), C[i](1 \le C[i] \le 20)V[i](1≤V[i]≤20),C[i](1≤C[i]≤20), representing the weight the i^{th}ith kind of ship can carry, and the number of the i^{th}ith kind of ship is 2^{C[i]} - 12C[i]−1.$

For the next $\le S \le 10000)S(1≤S≤10000), representing the queried weight.$

Output

For each query, output one line containing a single integer which represents the number of schemes for arranging ships. Since the answer may be very large, output the answer modulo

样例输入复制

11 22 112

样例输出复制

题目来源

题意：

有n种船每种有2^c[i] - 1艘每艘载重v[i]【必须完全装满】

现给出q次查询s 输出装载s的安排船的方案数

思路：

形如多重背包问题用二进制的思想就行优化

dp[w]表示载重w时的方案数他可由dp[w - v[i] * k]得到其中k是系数

按照二进制的思想每次k*=2 最多20次并且判断和c[i]的关系

要注意因为是2^c[i] -1因此等号不能取

1 // ConsoleApplication3.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。 2 // 3  4 //#include "pch.h" 5 #include 
     
       6 #include
      
        7 #include
       
         8 #include
        
          9 #include
         
          10 #include
          
           11 #include
           12 #include
            
             13 #include
             
              14 #include
              
               15 16 #define inf 0x3f3f3f3f17 18 using namespace std;19 typedef long long LL;20 21 const int maxn = 25;22 const int maxs = 10005;23 const LL mod = 1000000007;24 int t, n, q, s;25 int v[maxn], c[maxn];26 LL dp[maxs];27 28 int main()29 {30 cin >> t;31 while (t--) {32 scanf("%d%d", &n, &q);33 for (int i = 0; i < n; i++) {34 scanf("%d%d", &v[i], &c[i]);35 }36 37 memset(dp, 0, sizeof(dp));38 dp[0] = 1;39 40 int k = 1;41 for (int j = 0; j < 20; j++) {42 for (int i = 0; i < n; i++) {43 if (j >= c[i]) {44 continue;45 }46 for (int w = maxs; w >= v[i] * k; w--) {47 dp[w] += dp[w - k * v[i]];48 dp[w] %= mod;49 }50 }51 k *= 2;52 }53 54 while (q--) {55 scanf("%d", &s);56 printf("%lld\n", dp[s]);57 }58 }59 }

转载于:https://www.cnblogs.com/wyboooo/p/9674389.html

你可能感兴趣的文章

Strict Standards: Only variables should be passed by reference