1.题目
2.题目大意
一个天平上有一些钩子，现在有一些砝码。给出每个钩子到原点（姑且这么叫吧）的距离(-15 ~ 15，负数代表在左边，正数相反)以及砝码的重量(1 ~ 20)，求出把所有的砝码挂上天平并且让天平保持平衡的方案数。
3.分析
显然，暴力枚举必然会TLE。那么，看到 方案总数四个数就想到了数论和DP。
在这道题里，可以看出要用DP。
设(f_{i,j})为：把前 (i) 个砝码全部放到天平，倾斜度为 (j) 的方案总数。
规定正数为向右偏，负数为向左偏。
这里讲一下输入数据对于答案的贡献：如果第 (i) 个砝码放在 (dis_k) 的位置时，它的倾斜度为： dis[k]*wei[i]。
那么，必然有负数下标，所以改用Pascal所以要把所有 (j) 加上一个数，使得全是正数。考虑题目的极限数据：距离范围最大15，重量范围最大25，个数范围最大20，所以极限倾斜度为：(15 \times 25 \times 20=7500)。所以，所有的 (j) 都要加上7500。答案为：(f_{n,7500})。
假设我们已经成功的推出了 (f_{i-1,j}) 考虑转移方程。显然，我们可以枚举第 (i) 个砝码的位置，所以所有的位置都要试一遍。假设我们放在第 (k) 个位置，(j=j+dis_k \times wei_i)。那么，现在仅仅是多放第 (i) 个砝码在第 (k) 个位置，所以方案数是没有变动的。换而言之，(f_{i,j+dis_k \times wei_i})是要继承(f_{i-1,j})的方案总数的。
注意，这里我们是 (f_{i-1,j} \to f_{i,j+dis_k \times wei_i}) 的，因为 (k) 是有变动的，所以 (f_{i-1,j})有对多个状态有贡献。它们必然会形成一张复杂的网，那么对同一个状态重复贡献，所以需要把贡献给加起来。其实最好的办法就是当 (f_{i-1,j} \to f_{i,j+dis_k \times wei_i})时，做一个操作 f[i][j+dis[k]*wei[i]]+=f[i-1][j]。
4.代码
如果还是看不懂，看看代码吧。
抄袭可耻！！！
for(int i=1;i
#include
#include
using namespace std;
int m,n,dis[23],wei[23],f[23][15003];
int main()
{
scanf("%d%d",&m,&n);
for(int i=1;i
5.参考文献
Original: https://www.cnblogs.com/xmtxlym/p/15628572.html
Author: 小铭同学lym
Title: [题解]Balance
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/587729/
转载文章受原作者版权保护。转载请注明原作者出处！