天平（balance.in/balance.out） 物理老师YJ有一个长杆天平，天平的两臂长均为15，将长杆看作x轴，则平衡点在0位置处，负数位置在左臂上，正数位置在右臂上。长杆上有n个位置有挂钩可以挂秤砣。YJ有m个秤砣，质量分别为gi，每个挂钩可以不挂也可以挂任意个秤砣。YJ想要知道，在使用所有秤砣的条件下，有多少种不同的挂秤砣的方案，可以使得天平平衡？问题太过复杂，仅凭物理知识难以解决，所以请你来帮助他。 天平的平衡条件是所有秤砣的位置质量之和为0。例如有质量为2,3,4的秤砣分别挂在-3,-2,3位置处，则2(-3) + 3*(-2) + 4*3 == 0，天平是平衡的。 【输入格式】 第一行两个数n，m。表示挂钩的数目和秤砣的数目。 第二行n个不同且递增的数，第i个数表示第i个挂钩的位置，数的范围在[-15,15]内。 第三行m个不同且递增的数，第i个数表示第i个秤砣的质量，数的范围在[1,25]内。 【输出格式】 一个整数，代表能使得天平平衡的方案数。 【输入样例】 2 4 -2 3 3 4 5 8 【输出样例】 2 【样例解释】 方案1: (-2)*(3+4+5) + 3*8 = 0 方案2: (-2)(4+8) + 3(3+5) = 0 【数据规模】 10% 数据满足2≤n,m≤4。 100% 数据满足2≤n,m≤20。 【解法】 简单的DP。考虑天平的状态可以用秤砣质量距离来表示，而题目情况下，天平的全部秤砣质量距离在(-7500,7500)(20*25*15 = 7500)以内。故可以以此状态来dp。 类似背包问题，把每一个秤砣挂在不同地方，对应成n*m个物品，转移方程f[i][j]+=f[i-1][j-dis[k]*mg[i]] (i=1..n,j=0..15000,k=1..m)。
#include<iostream> #include<cstdio> #include<cstring> #include<string> #include<set> #include<queue> #include<algorithm> #include<vector> #include<cstdlib> #include<cmath> #include<ctime> #include<stack> #define INF 2100000000 #define LL long long #define clr(x) memset(x,0,sizeof(x)) #define ms(a,x) memset(x,a,sizeof(x)) #ifdef win32 #define AUTO "%I64d" #else #define AUTO "%lld" #endif using namespace std; const int maxn = 25; int n,m; LL c[maxn],t[maxn]; LL dp[maxn][15005]; template <class T> inline void read(T &x) { int flag = 1; x = 0; char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-') flag = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') { x = (x<<1)+(x<<3)+ch-'0'; ch = getchar(); } x *= flag; } int main() { freopen("balance.in","r",stdin); freopen("balance.out","w",stdout); read(n); read(m); for(int i = 1; i <= n; i++) read(t[i]); for(int i = 1; i <= m; i++) read(c[i]); dp[0][7500] = 1; for(int i = 1; i <= m; i++) for(int k = 1; k <= n; k++) for(int j = 0; j <= 15000; j++) { if(j-t[k]*c[i] < 0 || j-t[k]*c[i] > 15000) continue; dp[i][j] += dp[i-1][j-t[k]*c[i]]; } cout << dp[m][7500] << endl; return 0; }