小M和天平

$\mathrm{对}\mathrm{于}\mathrm{这}\mathrm{题}\mathrm{来}\mathrm{说},\mathrm{难}\mathrm{点}\mathrm{在}\mathrm{于}\mathrm{分}\mathrm{析}\mathrm{左}\mathrm{右}\mathrm{两}\mathrm{边}\mathrm{的}\mathrm{天}\mathrm{平}\mathrm{.}\mathrm{但}\mathrm{是}\mathrm{我}\mathrm{们}\mathrm{可}\mathrm{以}\mathrm{发}\mathrm{现},\mathrm{把}\mathrm{这}\mathrm{个}\mathrm{石}\mathrm{头}\mathrm{放}\mathrm{负}\mathrm{数}\mathrm{边}\mathrm{其}\mathrm{实}\mathrm{就}\mathrm{是}abs(j-x)\mathrm{.}\{对于这题来说,难点在于分析左右两边的天平.但是我们可以发现,把这个石头放负数边其实就是abs(j-x).\}$ $\mathrm{对}\mathrm{此}\mathrm{我}\mathrm{们}\mathrm{令}:f[i][j]\mathrm{为}\mathrm{到}\mathrm{了}\mathrm{第}i\mathrm{个}\mathrm{能}\mathrm{否}\mathrm{组}\mathrm{成}j\mathrm{.}\{对此我们令:f[i][j]为到了第i个能否组成j.\}$ $\mathrm{三}\mathrm{个}\mathrm{转}\mathrm{移}\mathrm{方}\mathrm{程}:\{三个转移方程:\}$ $f[i][j]+=f[i-1][j];\{f[i][j]+=f[i-1][j];\}$ $f[i][j+x]+=f[i-1][j];\{f[i][j+x]+=f[i-1][j];\}$ $f[i][abs(j-x)]+=f[i-1][j];\{f[i][abs(j-x)]+=f[i-1][j];\}$ 代码如下:

#include <bits stdc++.h>
using namespace std;
const int M=105,N=1e4+50;
bool f[M][N];
int main()
{
	int n;
	while(scanf("%d",&amp;n)!=EOF)
	{
		int m=10000;
		for(int i=0;i&lt;=n;i++)	f[i][0]=true;
		for(int i=1;i&lt;=n;i++)
		{
			int x;scanf("%d",&amp;x);
			for(int j=0;j&lt;=m;j++)
			{
				if(f[i-1][j])
				{
					f[i][j]=true;
					f[i][j+x]=true;
					f[i][abs(j-x)]=true;
				}
			}
		}int q;scanf("%d",&amp;q);
		while(q--)
		{
			int x;scanf("%d",&amp;x);
			if(x&gt;m||!f[n][x])	puts("NO");
			else				puts("YES");
		}
		memset(f,false,sizeof f);
	}
}
```</bits>