#include<iostream>
#include<cstring>
using namespace std;
int dp[100001];
int myMax(int x,int y)
{
	return x>y?x:y;
}
void MultiPack(int cash,int nk,int dk)
{
	int i,k;
	if(nk*dk>=cash)
	{
		for(i=dk;i<=cash;i++)
			dp[i]=myMax(dp[i],dp[i-dk]+dk);
		return;
	}
	k=1;
	while(k<nk)
	{
		for(i=cash;i>=k*dk;i--)
			dp[i]=myMax(dp[i],dp[i-dk*k]+dk*k);
		nk-=k;
		k<<=1;
	}
	k=nk;
	for(i=cash;i>=k*dk;i--)
		dp[i]=myMax(dp[i],dp[i-dk*k]+dk*k);
}
int main()
{
	int cash,n,nk,dk;
	while(!cin.eof())
	{
		memset(dp,0,sizeof(dp));
		cin>>cash>>n;
		while(n)
		{
			cin>>nk>>dk;
			MultiPack(cash,nk,dk);
			n--;
		}
		cout<<dp[cash]<<endl;
	}
	return 0;
}

• Re:why wa???????????????? (100) fresh_bird 2012-12-06 17:16:01
  • Re:why wa???????????????? (104) monkeyduck 2013-09-24 17:01:32
    • Re:why wa???????????????? (17) monkeyduck 2013-09-24 17:02:03