[POJ1837]-Balance

最新推荐文章于 2022-10-30 10:59:58 发布

Aelsy

最新推荐文章于 2022-10-30 10:59:58 发布

阅读量374

点赞数

分类专栏： Acm之dp(动态规划) 文章标签： 01背包 dp

Acm之dp(动态规划) 专栏收录该内容

6 篇文章

订阅专栏

Balance

Time Limit: 1000MS		Memory Limit: 30000K
Total Submissions: 13415		Accepted: 8393

Description

Gigel has a strange "balance" and he wants to poise it. Actually, the device is different from any other ordinary balance.
It orders two arms of negligible weight and each arm's length is 15. Some hooks are attached to these arms and Gigel wants to hang up some weights from his collection of G weights (1 <= G <= 20) knowing that these weights have distinct values in the range 1..25. Gigel may droop any weight of any hook but he is forced to use all the weights.
Finally, Gigel managed to balance the device using the experience he gained at the National Olympiad in Informatics. Now he would like to know in how many ways the device can be balanced.

Knowing the repartition of the hooks and the set of the weights write a program that calculates the number of possibilities to balance the device.
It is guaranteed that will exist at least one solution for each test case at the evaluation.

Input

The input has the following structure:
• the first line contains the number C (2 <= C <= 20) and the number G (2 <= G <= 20);
• the next line contains C integer numbers (these numbers are also distinct and sorted in ascending order) in the range -15..15 representing the repartition of the hooks; each number represents the position relative to the center of the balance on the X axis (when no weights are attached the device is balanced and lined up to the X axis; the absolute value of the distances represents the distance between the hook and the balance center and the sign of the numbers determines the arm of the balance to which the hook is attached: '-' for the left arm and '+' for the right arm);
• on the next line there are G natural, distinct and sorted in ascending order numbers in the range 1..25 representing the weights' values.

Output

The output contains the number M representing the number of possibilities to poise the balance.

Sample Input

2 4	
-2 3 
3 4 5 8

Sample Output

题目描述：

有一个天平，给你挂钩(-+代表左右的挂钩)和砝码（按照升序格式提供数据），求得能获得多少种方式使得太平平衡，要求用完所有的砝码，但是不一定用完所有的挂钩。

解题思路：

将所有的情况枚举出来判断出来判断是否平衡，结果你懂的（TLE），这里需要用dp来进行优化，先考虑极端的情况想15*25*20=7500,得到其区间为（-7500,7500）所有想用数组解决问题，就不能用0来当做平衡度，可以将7500当做平横度，这样如有-7500这种情况也能处理。

这里用所有的砝码都要用，采用的01背包思想（每个砝码只能用一次）

每次加砝码时判断前面i-1个砝码是否能表示j重量状态（判断其是否为0就ok），这样优化很大程度上的减少时间消耗

//head.h
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <cmath>
#include <ctime>
#include <algorithm>
#include <string>
#include <memory>
#include <string>
#include <list>
#include <queue>
#include <deque>
#include <vector>
#include <stack>
#include <utility>
#include <set>
#include <map>
#include <iterator>
#include <fstream>
using namespace  std;

#include "head.h"
const int maxn = 15001;
int hook[maxn];
int fama[maxn];
int dp[22][maxn];
int main()
{
	int c,g;
	while(~scanf("%d%d",&c,&g))
	{
		for(int i = 1;i <= c;++ i)
			scanf("%d",hook+i);
		for(int i = 1;i <= g;++ i)
			scanf("%d",fama+i);
		memset(dp,0,sizeof(dp));
		dp[0][7500]=1;//将7500作为一个平衡度（没使用砝码）
		for(int i = 1;i <= g;++ i)//每种只能砝码都用到，并只能用一次（01背包）
			for(int j = 0;j<=15000;++ j)
				if(dp[i-1][j])
					for(int k = 1;k <= c;++ k)//动态规划（dp）
						dp[i][j+hook[k]*fama[i]] += dp[i-1][j];//增加状态
		cout << dp[g][7500] << endl;
	}
	return 0;
}