POJ 1742 Coins(マルチバックパック|モノトーンキュー最適化)

パケットを分割してTLEについて、単調なキュー最適化を学び、具体的にはコードの注釈に書きます.
LTCに奋闘した男は八题、二日二题、男は1/4、生物は3/4となったので...今までは陰陽人か人妖か分からなかった...
下のはもし8題を解いていないでよく考えてから私を噴き出します...

/*
                    ，           ，ORZ LTC。。。
            ，    n   ，      a[i],   c[i],          m    
          ，     ，   TLE。。。      ，    ——>      
           ：
      c[i]=1 01     
     a[i]*c[i]>=m        
              ：
               i   ，  dp[i]             j
        dp[j]=1&&(i-j)%a[i]==0&&(i-j)/a[i]<=c[i]
             ，      ，                  ，         
                  que ，                
          sum           
          sum>0           
             ，  que sum
*/
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

#define N 100
#define M 100010
int a[N];
int c[N];
bool dp[M],que[M];

int main(){
    int i,j,k,n,m,tot;
    while(scanf("%d %d",&n,&m)!=EOF&&n+m){
        for(i=0;i<n;i++){
            scanf("%d",&a[i]);
        }
        for(i=0;i<n;i++){
            scanf("%d",&c[i]);
        }
        memset(dp,0,sizeof(dp));
        dp[0]=1;
        int ret=0;
        for(i=0;i<n;i++){
            if(c[i]==1){    //01  
                for(j=m;j>=a[i];j--){
                    if(!dp[j]&&dp[j-a[i]]){
                        dp[j]=1;
                        ret++;
                    }
                }
            }
            else if(c[i]*a[i]>=m){   //    
                for(j=a[i];j<=m;j++){
                    if(!dp[j]&&dp[j-a[i]]){
                        dp[j]=1;
                        ret++;
                    }
                }
            }
            else{
                for(j=0;j<a[i];j++){
                    int s=0,e=-1,sum=0;
                    for(k=j;k<=m;k+=a[i]){
                        if(s+c[i]==e){
                            sum-=que[s++];
                        }
                        sum+=dp[k];
                        que[++e]=dp[k];
                        if(!dp[k]&&sum){
                            dp[k]=1;
                            ret++;
                        }
                    }
                }
            }
        }
        printf("%d
",ret);
    }
    return 0;
}