4835688_ac_422ms_476k.cpp

部分PKU上的源码

#include<iostream>
using namespace std;
int goal,n,best;
int v[11],p[11];
bool can[100005];
bool fcan[100005];
int cl;
void testout()
{
	for(int j=0;j<=goal;j++)if(can[j]) cout<<j<<" ";
	cout<<endl;
}
void getit()
{
	int i,j,k,temp;
	memset(can,0,sizeof(can));
	can[0]=true;
	cl=1;
	for(i=0;i<n;i++)
	{
		memset(fcan,0,sizeof(fcan));
		for(j=0;j<=goal;j++)
		{
			if(can[j])
			{
				temp=j+v[i];
				for(k=1;k<=p[i];k++,temp+=v[i])
				{
					if(temp>goal) break;
					if(temp==goal) {cout<<goal<<endl;return;}
					if(temp>best) best=temp;
					fcan[temp]=true;
				}
			}
		}
		for(j=0;j<=goal;j++) if(fcan[j]) can[j]=true;
		//testout();
	}
	cout<<best<<endl;
}
int main()
{
	int i;
	while(cin>>goal)
	{
		cin>>n;
		for(i=0;i<n;i++)cin>>p[i]>>v[i];
		best=0;
		getit();
		//dfs(0,p[0],0);
	}
	return 0;
}