4835654_wa.cpp

来自「部分PKU上的源码」· C++ 代码 · 共 42 行

#include<iostream>
using namespace std;
int goal,n,best;
int v[11],p[11];
bool can[100005];
void getit()
{
	int i,j,k,temp;
	memset(can,false,sizeof(can));
	can[0]=true;
	for(i=0;i<n;i++)
	{
		for(j=0;j<=goal;j++)
		{
			if(can[j])
			{
				temp=j;
				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;
					can[temp]=true;
				}
			}
		}
	}
	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;
}