昨天复习了下动态规划的基本知识，然后就拿了这道题来AA。
题目的本质是求方程A1X1+A2X2+A3X3+......+AnXn=0解的个数。其中Ai表示挂钩离源点的距离，Xi表示物品重量（注意：某些Ai值可以相等，如可能出现A1=A5）。
看到数据量（c<=20,g<=20）时有种想用搜索的冲动，但是想了想实现的算法，发现搜索解决不了，枚举数量是20^n——太大啦！！！。
于是只能用DP了，DP方程如下f[v]=f[i-1][v-valure]+f[v]，数组f初始化为零，由于会出现负数，所以数组需要些小处理，详情见代码：
#include <iostream>
#define N 7500
using namespace std;
int c,g,i,j,k,valure,x[20],w[20],f[20][15002];
int main()
{
cin>>c>>g;
for(i=0;i<c;i++)
cin>>x[i];
for(i=0;i<g;i++)
cin>>w[i];
memset(f,0,sizeof(f));
for(i=0;i<c;i++)
f[0][w[0]*x[i]+N]=1;
for(i=1;i<g;i++)
for(j=0;j<c;j++)
{
valure=w[i]*x[j];
for(k=valure;k<15001;k++)
f[i][k]+=f[i-1][k-valure];
}
cout<<f[g-1][N]<<endl;
}
看到代码是不是很无语啊- -，这么短！！！是的，就是这么短，但是这个DP却不好想，得先转化，然后就是递推求解了。
DP—— 一定要注重分析，写出了方程就成功了一般。