#include <iostream>

using namespace std;

long bPos[21],bNeg[21],w[21],pos[4000],neg[4000],nPos[4000],nNeg[4000],markPos[4000],nMarkPos[4000],markNeg[4000],nMarkNeg[4000];

int main()
{
	//freopen("p.txt","r",stdin);
	//freopen("s.txt","w",stdout);
	long b,c,g,i,j,k,bPosNum,bNegNum,tmp,posTail,nPosTail,negTail,nNegTail;
	while(cin>>c>>g)
	{
		bNegNum=0;
		bPosNum=0;
		for(i=1;i<=c;i++)//输入挂钩的位置
		{
			cin>>b;
			if(b<0) bNeg[++bNegNum]=b;//小于0的放到数组bNeg中
			else bPos[++bPosNum]=b;//大于等于0的放到数组bPos中
		}
		for(i=1;i<=g;i++) cin>>w[i];//输入砝码的重量
		memset(pos,0,sizeof(pos));//初始化位置标量
		memset(neg,0,sizeof(neg));
		pos[0]=1;//为了让第一组数据找到切入点
		neg[0]=1;
		markNeg[0]=0;//位置标量的下标初始化
		markPos[0]=0;
		negTail=0;//下标末尾位置初始化
		posTail=0;
		for(i=1;i<g;i++)//循环g-1件砝码
		{
			nPosTail=-1;//初始化  下一个砝码放的时候   记录有值位置的数组   的末尾
			nNegTail=-1;
			memset(nPos,0,sizeof(nPos));//初始化  下一个砝码放的时候  标记可达数目的数组
			memset(nNeg,0,sizeof(nNeg));
			for(j=1;j<=bNegNum;j++)//循环所有为负的挂钩
			{
				tmp=-bNeg[j]*w[i];//得到相应的值
				for(k=0;k<=negTail;k++)//找所有小于0的位置
					if(neg[markNeg[k]])//如果这个位置有值
					{
						if(nNeg[markNeg[k]+tmp]==0) nMarkNeg[++nNegTail]=markNeg[k]+tmp;//放砝码后的值没有被填充过，就将这个值放到标记下标的数组
						nNeg[markNeg[k]+tmp]+=neg[markNeg[k]];//加上这种方法增加的可达数
					}
				for(k=0;k<=posTail;k++)//所有大于0的位置
					if(pos[markPos[k]])//如果这个位置有值
					{
						if(markPos[k]-tmp>=0)//没有跨越0
						{
							if(nPos[markPos[k]-tmp]==0) nMarkPos[++nPosTail]=markPos[k]-tmp;//放砝码后的值没有被填充过，就将这个值放到标记下标的数组
							nPos[markPos[k]-tmp]+=pos[markPos[k]];//加上这种方法增加的可达数
						}
						else//跨越了0
						{
							if(nNeg[tmp-markPos[k]]==0) nMarkNeg[++nNegTail]=tmp-markPos[k];
							nNeg[tmp-markPos[k]]+=pos[markPos[k]];
						}
					}
			}
			for(j=1;j<=bPosNum;j++)//所有为正的挂钩
			{
				tmp=bPos[j]*w[i];
				for(k=0;k<=negTail;k++)
					if(neg[markNeg[k]])
					{
						if(tmp-markNeg[k]<=0)
						{
							if(nNeg[markNeg[k]-tmp]==0) nMarkNeg[++nNegTail]=markNeg[k]-tmp;
							nNeg[markNeg[k]-tmp]+=neg[markNeg[k]];
						}
						else
						{
							if(nPos[tmp-markNeg[k]]==0) nMarkPos[++nPosTail]=tmp-markNeg[k];
							nPos[tmp-markNeg[k]]+=neg[markNeg[k]];
						}
					}
				for(k=1;k<=posTail;k++)
					if(pos[markPos[k]])
					{
						if(nPos[markPos[k]+tmp]==0) nMarkPos[++nPosTail]=markPos[k]+tmp;
						nPos[markPos[k]+tmp]+=pos[markPos[k]];
					}
			}
			negTail=nNegTail;
			posTail=nPosTail;
			if(nMarkNeg[0]!=0) nMarkPos[0]=nMarkNeg[0];
			else if(nMarkPos[0]!=0) nMarkNeg[0]=nMarkPos[0];
			for(j=0;j<=negTail;j++) markNeg[j]=nMarkNeg[j];
			for(j=0;j<=posTail;j++) markPos[j]=nMarkPos[j];
			memset(neg,0,sizeof(neg));
			memset(pos,0,sizeof(pos));
			for(j=0;j<=negTail;j++) neg[markNeg[j]]=nNeg[markNeg[j]];
			for(j=0;j<=posTail;j++) pos[markPos[j]]=nPos[markPos[j]];
		}
		int ans=0;
		for(j=1;j<=bNegNum;j++)
		{
			tmp=bNeg[j]*w[g];
			ans+=pos[-tmp];
		}
		for(j=1;j<=bPosNum;j++)
		{
			tmp=bPos[j]*w[g];
			ans+=neg[tmp];
		}
		cout<<ans<<endl;
	}
	return 0;
}

• 总算过了…… 想的太复杂了，重写了代码…… (21) goodness 2008-07-28 16:23:02
  • Re:总算过了…… 想的太复杂了，重写了代码…… (807) sxow1234 2010-12-04 22:35:39