求方案，爆大数据，M稍微大就会爆2^64，不可取，但值得学习

tsum表示当前队列的和，有f[i][j] = tsum + f[i-1][j],其中f[i-1][j]就为g[j];
不断维护tsum就行

#include <iostream>
#include <cstring>
using namespace std;
const int N = 110;
const int M = 1e5+10;

int n,m;
int v[N],c[N];
int f[M],g[M];

int main(){
    ios::sync_with_stdio(0);
    while(cin >> n >> m,n){
        for(int i = 1; i <= n; i++){
            cin >> v[i];
        }
        for(int i = 1; i <= n; i++){
            cin >> c[i];
        }

        memset(f,0,sizeof(f));
        f[0] = 1;
        int q[M];
        for(int i = 1; i <= n; i++){
            memset(q,0,sizeof(q));
            memcpy(g,f,sizeof(g));
            for(int r = 0; r < v[i]; r++){
                int hh = 0, tt = -1;
                int tsum = 0;
                for(int j = r; j <= m; j += v[i]){
                    while(hh <= tt && j-q[hh] > c[i]*v[i]){tsum-=g[q[hh]];hh++;}
                    f[j] = g[j] + tsum; 
                    q[++tt]=j;
                    tsum+=g[j];
                }
            }
        }

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

求有无方案

while循环对头判断有没有超过c[i]
如果g[j]和队列里有一个为1，即队列非空，则有解赋值g为1
最后判断f数组里面1的个数就行

#include <iostream>
#include <cstring>
using namespace std;
const int N = 110;
const int M = 1e5+10;
int n,m;
int v[N],c[N];
int f[M],g[M];
#pragma GCC optimize(3)
#pragma GCC optimize(2)
#pragma GCC optimize(1)
int main(){
    while(scanf("%d %d", &n, &m),n || m){
        for(int i = 1; i <= n; i++){
            scanf("%d",&v[i]);
        }
        for(int i = 1; i <= n; i++){
            scanf("%d",&c[i]);
        }

        memset(f,0,sizeof(f));
        f[0] = 1;
        for(int i = 1; i <= n; i++){
            memcpy(g,f,sizeof(g));
            int q[M];
            for(int r = 0; r < v[i]; r++){
                int hh = 0, tt = -1;
                for(int j = r; j <= m; j += v[i]){
                    while(hh <= tt && j-q[hh] > c[i]*v[i])hh++;
                    if(g[j])q[++tt] = j;
                    if(hh<=tt)f[j] = 1;
                }
            }
        }

        int res = 0;
        for(int i = 1; i <= m; i++){
            if(f[i] > 0)res++;
        }
        printf("%d\n",res);
    }
    return 0;
}