均衡

描述：

吉格尔有一种奇怪的“平衡”，他想保持平衡。实际上，该设备不同于任何其他普通天平。

它订购了两条重量可以忽略不计的手臂，每条手臂的长度为15。一些钩子连接到这些手臂上，Gigel想挂起他收集的G重量（1<=G<=20）中的一些重量，因为知道这些重量在1范围内有不同的值。。25.Gigel可以放下任何钩子的任何重量，但他必须使用所有重量。

最后，Gigel利用在全国信息学奥林匹克运动会上获得的经验，成功地平衡了设备。现在他想知道该设备可以通过多少种方式实现平衡。

 

了解挂钩的重新分配和重量设置，编写一个程序，计算平衡装置的可能性数量。

保证在评估时，每个测试用例至少存在一个解决方案。

输入：

输入具有以下结构：

•第一行包含数字C（2<=C<=20）和数字G（2<=G<=20）；

•下一行包含-15范围内的C整数（这些数字也不同，并按升序排序）。。15代表吊钩的重新分配；每个数字代表相对于X轴上天平中心的位置（当未连接砝码时，装置平衡并与X轴对齐；距离的绝对值表示吊钩与平衡中心之间的距离，数字符号确定吊钩连接的天平臂：“-”表示左臂，“+”表示右臂）；

•下一行有G个自然的、不同的、按升序排列的数字，范围为1。。25表示权重值。

输出：

输出包含数字M，代表平衡平衡的可能性数量。

样例输入：

2 4

-2 3

3 4 5 8

复制

样例输出：

2

大佬的讲解博客：https://www.cnblogs.com/lyy289065406/archive/2011/07/31/2122629.html；

这道题最让我没想到的是居然可以在不是求最优解的题目中用动态规划；

根据大佬的说法好像其使用条件是：

 

dp思路：

每向天平中方一个重物，天平的状态就会改变，而这个状态可以由若干前一状态获得。

 

一开始我也想的是枚举，但算一下就知道会超时；然后我傻了，不知所措；

但看了题解才知道用动态规划，我就在想为什么动态规划就比枚举会快这么多呢？动态规划也不是有枚举吗？

可能是结构不同：枚举可能有时在某一部分相同的地方枚举太多次了；

而动态规划却可以保存重复的地方，精确枚举出真正要的地方，且只枚举一次；

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<cstring>
 5 using namespace std;
 6 int hookplace[25],weight[25];
 7 int dp[25][15000];
 8 int main()
 9 {
10     int hooknum,weightnum;
11     cin>>hooknum>>weightnum;
12     for (int i=1;i<=hooknum;i++)
13     {
14         cin>>hookplace[i];
15     }
16     for (int j=1;j<=weightnum;j++)
17     {
18         cin>>weight[j];
19     }
20     memset (dp,0,sizeof (dp));
21     dp[0][7500]=1;
22     for (int i=1;i<=weightnum;i++)
23     {
24         for (int j=1;j<=hooknum;j++)
25         {
26             for (int k=0;k<=15000;k++)
27             {
28                 if (dp[i-1][k]!=0)
29                 {
30                     dp[i][k+weight[i]*hookplace[j]]+=dp[i-1][k];
31                 }
32             }
33         }
34     }
35     cout<<dp[weightnum][7500];
36     return 0;
37 }