poj 1837 Balance dp

缘起

dp博大精深~ poj 1837 Balance

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
给你c（2<=c<=20）个挂钩，g（2<=g<=20）个砝码，求在将所有砝码(所有砝码都要挂上~)（砝码重1~~25）
挂到天平(天平长  -15~~15)上，并使得天平平衡的方法数

【输入】
本题只用处理一组数据. 第一行是c和g, 然后c个整数（这些数形成严格单增的序列）表示挂钩的位置.
然后是g个正整数代表砝码的重量。

【输出】
平衡天平的方法数

【样例输入】
2 4	
-2 3 
3 4 5 8

【样例输出】
2

【限制】
1s

解决方法依旧是dp. 而dp的状态是右力矩减去左力矩的差值(下面简称差值). 

1
2
3
4
5
6
7
令dp[i][j] 是仅仅考虑前i个砝码的时候, 差值为j的方法数. 则
dp[i][j] = sigma_{k个挂钩} dp[i-1][j-g[i]*c[k]](即第i个砝码g[i]挂在了第k个挂钩上)
初始值是dp[0][0] = 1, dp[0][j]=0(-7500<=j<=7500,且 j!=0), 即不选任何一个砝码的话,则差值为0的
方法数显然就是1, 即就是什么都不挂, 而要求力矩有非零差值这显然办不到,所以方法数是0
其中右力矩减去左力矩的最大值是25*20*15=7500, 最小值显然就是 -7500.
最后的答案是dp[c][0].
但是因为数组索引不能为负值, 所以要加上一个偏移量os=7500. 所以最后要求的是dp[c][7500]

于是不难写下如下代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
//#include "stdafx.h"
#include <stdio.h>
//#define LOCAL
const int os = 7500, maxc = 30;
int c,g, cc[maxc], gg[maxc], dp[maxc][os<<1];

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
//	freopen("d:\\my.out", "w", stdout);
#endif
	scanf("%d%d", &c, &g);
	for (int i = 1;i<=c;i++)
	{
		scanf("%d", cc+i);
	}
	for (int i = 1;i<=g;i++)
	{
		scanf("%d", gg+i);
	}
	dp[0][os] = 1;
	for (int i = 1;i<=g;i++)
	{
		for (int j = 0; j<=os*2; j++)
		{
			for (int k = 1;k<=c;k++)
			{
				dp[i][j]+=dp[i-1][j-gg[i]*cc[k]];
			}
		}
	}
	printf("%d", dp[g][os]);
	return 0;
}

ac情况

Status Accepted
Time 63ms
Memory 992kB
Length 577
Lang C++
Submitted 2019-10-27 10:34:04
Shared
RemoteRunId 20994500