4817539_ac_63ms_1960k.cpp

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

#include<iostream>
using namespace std;
int c[22],g[22];
int mem[22][2][10005];
int cl,gl;
int dp(int now,int w)
{
	if(now<0)
	{
		if(w==0) return 1;
		else return 0;
	}
	if(w>=0)
	{
		if(mem[now][1][w]!=-1) return mem[now][1][w];
	}
	else
	{
		if(mem[now][0][0-w]!=-1) return mem[now][0][0-w];
	}
	int i,re;
	re=0;
	for(i=0;i<cl;i++)
	{
		re+=dp(now-1,w-g[now]*c[i]);
	}
	if(w>=0) mem[now][1][w]=re;
	else mem[now][0][0-w]=re;
	return re;
}
int main()
{
	cin>>cl>>gl;
	int i;
	memset(mem,-1,sizeof(mem));
	for(i=0;i<cl;i++) cin>>c[i];
	for(i=0;i<gl;i++) cin>>g[i];
	cout<<dp(gl-1,0)<<endl;
	return 0;
}