题目描述

blablabla

样例

blablabla

算法1

二进制拆分+01背包问题

其实可以简单归为第i个数的方案数。
但是这里不能写为f[j]=f[j]+f[j-AA[i]]
QAQ最开始就是这样写，导致报错，其原因在于j越大，方案数量越多，直接溢出了！！！导致答案不对。之后，我想的第一步就是参考之前的写法f[j]=(f[j]+f[j-AA[i]])%mod，但是依旧有问题，mod操作导致TTE。
所以最简单的方法就是参考现在的写法f[j]=f[j]||f[j-AA[i]]。用一个或操作来表达，毕竟我现在也只需要把1传达过去。

时间复杂度

参考文献

C++ 代码

//O3优化
#pragma GCC optimize(3)
#include<iostream>
#include<string.h>
using namespace std;

const int N = 1e6+10;
int f[N];
int n,m;
int A[110],C[110];
int AA[N];
int main(){
    while(cin>>n&&cin>>m){
        memset(f,0,sizeof f);
        memset(AA,0,sizeof AA);
        if(n==0&&m==0){
            break;
        }
        for(int i=1;i<=n;i++){
            scanf("%d",&A[i]);
        }
        for(int i=1;i<=n;i++){
            scanf("%d",&C[i]);
        }
        //二进制优化
        int idx=1;
        for(int i=1;i<=n;i++){
            int k=1;            
            while(k<=C[i]){
                C[i]-=k;
                AA[idx]+=k*A[i];
                idx++;
                k<<=1;
            }
            if(C[i]>0){
                AA[idx]+=C[i]*A[i];
                idx++;
            }
        }
        n=idx;

        //01背包
        f[0]=1;
        for(int i=1;i<n;i++){
            for(int j=m;j>=AA[i];j--){
                f[j]=f[j]||f[j-AA[i]];
            }
        }

        int res=0;
        for(int j=1;j<=m;j++){
            if(f[j]>=1){
                res++;
            }
        }
        // cout<<f[99993]<<endl;
        cout<<res<<endl;
    }
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla