POJ1837-Balance
2021/11/10 23:16:20
本文主要是介绍POJ1837-Balance,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
POJ1837-Balance
题目链接:https://vjudge.net/problem/POJ-1837
题意:给你一根杠杆,轴在中心标记位0,中心左边,从左到右标记-15,-14,…,-1,中心右端,1,2,3,…,15,表示到中心的距离。现在给你c个挂钩,g个砝码。告诉你挂钩位置和每个砝码的重量,要求用完所有砝码。问:使得杠杆平衡的方案数是多少?
思路:动态规划。首先定义平衡度 b a l a n c e = Σ w [ i ] ∗ c [ k ] balance=Σw[i]*c[k] balance=Σw[i]∗c[k],w是砝码重量,c是砝码位置,显然当balance=0时,杠杆是平衡的。balance>0右端低,balance<0左端低。
定义: d p [ i ] [ j ] dp[i][j] dp[i][j]表示使用前i个砝码时,平衡度达到j时杠杆平衡的方案数。
放了i-1个砝码,平衡度为j时,状态为dp[i-1][j].
现在放第i个砝码:平衡度变为 j→j+w[i]*c[k].
此时放了i个砝码,平衡度为j+w[i]*c[k],状态为dp[i][j+w[i]*c[k]].
因为,末状态dp[i][j+w[i]*c[k]]可能由多个初状态得到所以要对dp[i-1][j]求和,不难得到
状态转移方程:
dp[i][j+w[i]*c[k]]=Σdp[i-1][j].
规划方向:采用自顶向下的方式。来求dp。循环变量及顺序(由外到内):j->w->c
目标答案:dp[cnt_w][7500]。(砝码用完时的平衡方案数)
代码:
#include<iostream> using namespace std; const int maxn=27; int dp[maxn][15001]; int w[maxn]; int c[maxn]; int main(){ int n_c,n_w; cin>>n_c>>n_w; int i; for(i=1;i<=n_c;i++)cin>>c[i]; for(i=1;i<=n_w;i++)cin>>w[i]; dp[0][7500]=1; int j,k; for(i=1;i<=n_w;i++){ for(j=0;j<=15000;j++){ for(k=1;k<=n_c;k++){ if(j+w[i]*c[k]>=0)dp[i][j+w[i]*c[k]]+=dp[i-1][j]; } } } cout<<dp[n_w][7500]<<endl; return 0; }
动态规划过程:
1.相关变量(如本题的w,c,平衡度,方案数)
2.定义dp(一维还是两维?dp i j的意思?)
3.暴力枚举简单解,确定状态转移方程
4.确定规划方向 ↑还是↓
5.目标答案的表达(放到第三步也行)
这篇关于POJ1837-Balance的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-09-28pyqt 怎么打包整个项目-icode9专业技术文章分享
- 2024-09-28laravel Commands 创建带有参数的 Artisan 命令的步骤和示例-icode9专业技术文章分享
- 2024-09-28antd怎么实现渲染tiff图片-icode9专业技术文章分享
- 2024-09-28英文半角中划线和中文全角的中划线有什么区别-icode9专业技术文章分享
- 2024-09-28nvm npm 和node 他们之间有什么关系-icode9专业技术文章分享
- 2024-09-28Node Version Manager (nvm)使用教程-icode9专业技术文章分享
- 2024-09-28nvm命令太慢,是什么原因-icode9专业技术文章分享
- 2024-09-28Kotlin 如何增加、删除和修改 MutableStateFlow 中的值。-icode9专业技术文章分享
- 2024-09-28Kotlin的stateFlow.update 写法介绍-icode9专业技术文章分享
- 2024-09-28kotlin 怎么获取当前时间格式-icode9专业技术文章分享