题意:一个天平,从左至右分别是-15到15的加权的钩子,给一些重量的物品,求有几种挂这些物品使天平平衡的方法个数。
思路:加权后重量的范围是-7500到7500。故枚举每个物品分别挂在每一个钩的状态,最后输出状态为0的个数
#include <iostream> #include <string> #include <cstring> #include <cmath> #include <algorithm> using namespace std; #define CL(a,b) memset(a,b,sizeof(a)) #define M 15000 #define LL unsigned __int64 int a[30],f[30],c,g; LL dp[30][M+1]; int main() { int i,j,k,l; while(scanf("%d%d",&c,&g)!=EOF) { for(i=0;i<c;i++) scanf("%d",&a[i]); for(i=0;i<g;i++) scanf("%d",&f[i]); CL(dp,0); for(i=0;i<c;i++) dp[0][f[0]*a[i]+7500]=1; for(j=1;j<g;j++) for(i=0;i<c;i++) for(k=0;k<=M;k++) if(dp[j-1][k]) dp[j][k+a[i]*f[j]]+=dp[j-1][k]; printf("%I64u\n",dp[g-1][7500]); } }