#include <iostream>
#include <algorithm>
using namespace std;

int A[128];
int C[128];
bool dp[100001];
int main(int argc, char *argv[])
{
	int n,m;
	while(cin>>n>>m && n||m)
	{
		for(int i=1;i<=n;++i)
			cin>>A[i];
		for(int i=1;i<=n;++i)
			cin>>C[i];
		
		memset(dp,0,sizeof(bool)*(m+1));
		dp[0]=true;
		for(int i=1;i<=n;++i)
		{
			if(C[i]*A[i]>=m)
			{
				for(int j=A[i];j<=m;++j)
					dp[j]|=dp[j-A[i]];
			}
			else
			{
				int k=1;
				int M=C[i];
				while(k<M)
				{
					for(int j=m;j>=k*A[i];--j)
						dp[j]|=dp[j-k*A[i]];
					M-=k;
					k*=2;
				}
				for(int j=m;j>=M*A[i];--j)
					dp[j]|=dp[j-M*A[i]];
			}
		
		} 
		cout<<count(dp+1,dp+m+1,true)<<endl;
	}
}

• Re:第一次1Adp问题。纪念个。附菜鸟2000+ms代码，求指教 (8) z85769597 2015-02-28 11:07:29