Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

第一次1Adp问题。纪念个。附菜鸟2000+ms代码,求指教

Posted by 1120121860 at 2013-07-16 11:14:46 on Problem 1742
#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;
	}
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator