id=1742" target="_blank">题目链接~~>

做题感悟：第一次做的时候用的二进制优化。可是没注意到是险过。so也没去看单调队列的解法。

解题思路：

假设你做过单调队列的题，或者看过相关的博客就好理解这题了。博客。

再加上这题体积与价值相等那么就更好做了。仅仅有 j %v[ i ] 余数同样的才干够同一时候处理（j 指的是某个体积的值），在计算某个数的时候，仅仅要计算前面的同样的余数中（在个数限制内）是否有
true（有放满的） 就能够了。

代码：

#include<iostream>

#include<sstream>

#include<map>

#include<cmath>

#include<fstream>

#include<queue>

#include<vector>

#include<sstream>

#include<cstring>

#include<cstdio>

#include<stack>

#include<bitset>

#include<ctime>

#include<string>

#include<cctype>

#include<iomanip>

#include<algorithm>

using namespace std  ;

#define INT long long int

#define L(x)  (x * 2)

#define R(x)  (x * 2 + 1)

const int INF = 0x3f3f3f3f ;

const double esp = 0.0000000001 ;

const double PI = acos(-1.0) ;

const int mod = 1000000007 ;

const int MY = (1<<5) + 5 ;

const int MX = 100010 + 5 ;

int n ,W ,ans ;

int v[MX] ,num[MX] ;

bool deq[MX] ,dp[MX] ;

void input()

{

    memset(dp ,false ,sizeof(dp)) ;

    for(int i = 1 ;i <= n ; ++i)

        scanf("%d" ,&v[i]) ;

    for(int i = 1 ;i <= n ; ++i)

        scanf("%d" ,&num[i]) ;

}

void DP(int v ,int num)

{

    if(!num || !v)  return ;

    if(num == 1) // 01 背包

    {

        for(int i = W ;i >= v ; --i)

           if(!dp[i] && dp[i-v])

               dp[i] = true ,ans++ ;

    }

    else if(num * v >= W) // 全然背包

    {

        for(int i = v ;i <= W ; ++i)

          if(!dp[i] && dp[i-v])

              dp[i] = true ,ans++ ;

    }

    else

    {

        num = min(num ,W/v) ;

        for(int a = 0 ;a < v ; ++a)  // 同样余数一块处理

        {

            int front =0 ,end = 0 ,sum = 0 ;

            for(int j = a ;j <= W ; j += v)

            {

                if(end - front-1 == num)  // 去除过时元素 ,由于最多选择num[i] 个

                    sum -= deq[front++] ;

                deq[end++] = dp[j] ;  // 存入

                sum += dp[j] ;

                if(!dp[j] && sum)

                    dp[j] = true ,ans++ ;

            }

        }

    }

}

int main()

{

    //freopen("input.txt" ,"r" ,stdin) ;

    while(scanf("%d%d" ,&n ,&W) ,n+W)

    {

        input() ;

        dp[0] = true ;

        ans = 0 ;

        for(int i = 1 ;i <= n ; ++i)

             DP(v[i] ,num[i]) ;

        printf("%d\n" ,ans) ;

    }

    return 0 ;

}