pku 1276 复数硬币问题.txt

ACM资料大集合

#include <stdio.h>
#include <iostream>
#include <stdio.h>
#include <stdio.h>
#include <iostream>
#include <math.h>
#include <stdlib.h>
#include <iomanip>
#include <string.h>
#include <algorithm>

//PKU 1276 复数硬币问题
using namespace std;
#define NMAX 150000
#define INFI 99999999
#define CMAX 11
int real[NMAX];//real[i],表示第i个货币值能否取到
int lleft[NMAX];//lleft[i],表示取到第i个货币后，还剩余的硬币数
int cashm[CMAX];//cashm[i],第i种硬币的面值
int cashn[CMAX];//cashn[i],第i种硬币的个数

void solve(int dnum,int totle)
{
	int i,j;
	memset(real,0,sizeof(real));
	real[0]=1;
	for(i=1;i<=dnum;i++)
	{
		memset(lleft,0,sizeof(lleft));
		for(j=0;j<=totle;j++)
		{
			if(1==real[j]) lleft[j]=cashn[i];//如果之前可以取到这个值，那么这一点的剩余硬币数等于一开始的硬币数
		}
		for(j=0;j<=totle;j++)
		{
			if(lleft[j]>0)
			{//这一点a有硬币
				real[j+cashm[i]]=1;//往后数，加上1个硬币的值b可以取到
				lleft[j+cashm[i]]=max(lleft[j]-1,lleft[j+cashm[i]]);//b的硬币数
			}
//			printf("lleft[%d]=%d real=%d\n",j,lleft[j],real[j]);
		}
	}
	for(i=totle;i>=0;i--)
	{
		if(real[i]==1) {printf("%d\n",i);return;}
	}
	return;
}

int main()
{
	int i,totle,dnum;
	while(scanf("%d %d",&totle,&dnum)!=EOF)
	{
		for(i=1;i<=dnum;i++) scanf("%d %d",&cashn[i],&cashm[i]);
		solve(dnum,totle);
	}
	return 0;
}