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.目标答案的表达(放到第三步也行)

上一篇:CF1242C-Sum Balance【状压dp】


下一篇:自定义对象流