尽可能多花钱 浙大2780.txt

ACM资料大集合

#include <iostream>
#include <iomanip>
#include <stdio.h>
using namespace std;

#define VMAX 32
#define MMAX 1002

long long f[VMAX][MMAX]={0};

int a[VMAX];

void init()
{
	int i,j;
	for(i=0;i<VMAX;i++)
	{
		a[i]=0;
		for(j=0;j<MMAX;j++)
			f[i][j]=0;
	}
}

void cal(int vmax,int mmax)
{	
	int i,j,sum;
	for(i=0;i<=vmax;i++) f[i][0]=0;
	for(i=0;i<=mmax;i++) f[0][i]=0;
	sum=0;
	for(i=1;i<=vmax;i++)
	{
		sum+=a[i];
		for(j=1;j<=mmax;j++)
		{
			if(j>=sum) {f[i][j]=1;continue;}
			if(a[i]>j) f[i][j]=f[i-1][j];
			else if(a[i]==j) f[i][j]=f[i-1][j]+1;
			else 
			{
				f[i][j]=f[i-1][j]+f[i-1][j-a[i]];
				if(f[i-1][j-a[i]]==0) f[i][j]++;
			}
		}
	}
}

int main()
{
	int N,limit,num,i,j;
	scanf("%d",&N);
	for(i=0;i<N;i++)
	{
		init();
		scanf("%d%d",&num,&limit);
		for(j=1;j<=num;j++)
			scanf("%d",&a[j]);
		cal(num,limit);
		printf("%d %lld\n",i+1,f[num][limit]);
	}
	return 0;
}

void print()
{
	int i,j;
	cout<<"  "; 
	for(i=0;i<MMAX;i++) printf("%-2d",i);
	cout<<endl;
	for(i=0;i<VMAX;i++)
	{
		cout<<i;
		for(j=0;j<MMAX;j++)
			printf("%2d",f[i][j]);
		cout<<endl;
	}
	cout<<endl;
//	system("pause");
}