题目:点击打开链接
题目大意:
有一个天平,天平左右两边的手臂长度都是15,手臂上面有些位置会有挂钩。还有G个砝码(1 <= G <= 20),它们重量各不相同,在1~25中取值。
给出C个挂钩,它们的位置在【-15..15】,不会重叠。负号的代表在左边臂,正号的在右边。
要求把所有砝码都放在挂钩上,多个砝码可以挂在同一个挂钩上,问有多少种不同的方案使天平能够平衡?
思路:
天平左臂的力矩和是负数,右边的力矩和是正数,那么左边+右边的力矩之和,如果是正数,代表天平平衡倾向右边,负数代表倾向左边,为0的时候天平是平衡的。我们把 “左边力矩和+右边力矩和”叫做平衡系数
状态f[i][j]代表用前i个砝码,放置成平衡系数为j的时候共有多少种方案。
那么,f[i][j] += f[i-1][j-C[k]*G[i]], {0<=k=<c};
因为平衡系数中有负数的,所以要所有平衡系数往右平移,即加上一个足够大的正数。可以计算出力矩之和最小负数的是把所有砝码都挂在天平-15的位置上,砝码最多20个,取值最大的情况是6...25,那么砝码之和最终为 (6+25)*20/2 = 310, 力矩之和为 -15*310 = 4650
所以加上4650即可,这是位置4650代表的是原来天平的中间位置,
初始化 f[0][4650] = 1, 表示一个砝码都不挂,这是一种平衡的方案。
最终,f[G][4650]就是答案。
PS: 这题最开始我是用滚动数组做的,用G++提交一直RE到死,郁闷。后来改用C++提交就可以AC了。
代码:
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#define SQ(x) ((x)*(x))
#define MP make_pair
const int INF = 0x3f3f3f3f;
const double PI = acos(-1.0);
typedef long long int64;
using namespace std;
const int MAXN = 22;
const int mid = 4650;
int pos[MAXN], w[MAXN];
int f[22][mid*2+10];
int n, m;
int main(){
while(~scanf("%d%d", &n, &m)){
for(int i=0; i<n; ++i)
scanf("%d", &pos[i]);
for(int i=0; i<m; ++i)
scanf("%d", &w[i]);
memset(f, 0, sizeof(f));
f[0][mid] = 1;
for(int i=0; i<m; ++i){
for(int j=0; j<n; ++j){
int add = w[i]*pos[j];
for(int v=mid*2; v-add>=0; --v){
if(v-add <= mid*2)
f[i+1][v] += f[i][v-add];
}
}
}
printf("%d\n", f[m][mid]);
}
return 0;
}
分享到:
相关推荐
北大POJ1837-Balance
POJ1837-Balance 解题报告+AC代码
关于poj dp分类,我一直寻找dp的分类,终于找到了,也上传一下
这是一道很不错的题目,dp解决的经典例子,是学习dp,和练习的好题目。。。。
经典的0-1背包问题. 适合新手学习. 原题网址:http://poj.grids.cn/problem?id=2773
POJ上的一道题目,自己写的代码,因为想下载别人的, 所以就放上了。
Poj 3342 这是一道树状dp题目,题意是这样的,一个公司,每个人有且仅有一个Boss,除了最大的Boss没有Boss(显然),现在要参加一个聚会,要求参加的人数最多,但是棘手的.......
这是黑不来就的poj上的所有dp题目的大型分类 好使好用
这道题关键是要能够表示出状态转移方程 从题目想到这一步不容易
背包之01背包、完全背包、多重背包详解 Dynamic+Programming 典型的动态规划,用递归下的记忆化搜索来实现 1088 POJ 动态规划加速原理之四边形不等式 基于连通性状态压缩的动态规划问题 对一些DP题目的小结 树型动态...
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
动态规划 01背包问题 POJ3624可以AC
北大POJ1015-Jury Compromise【动态规划DP】 解题报告+AC代码
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
POJ上的DP分类: 容易: 1018, 1050, 1083, 1088, 1125, 1143, 1157, 1163, 1178, 1179, 1189, 1208, 1276, 1322, 1414, 1456, 1458, 1609, 1644, 1664, 1690, 1699, 1740(博弈), 1742, 1887, 1926(马尔科夫矩阵,求...
poj.grids.cn题型汇总 Dp状态设计与方程总结 1.不完全状态记录 青蛙过河问题 利用区间dp 2.背包类问题 <1> 0-1背包,经典问题 无限背包,经典问题 判定性背包问题 带附属关系的背包问题 <5> + -1背包问题 ...
北大POJ3411-Paid Roads【class】 解题报告+AC代码
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
晒代码之二——多重背包(POJ1276)
poj分类poj分类poj分类poj分类