第十二届蓝桥杯省赛B组（C/C++）试题G砝码称重

题目

原题链接

---

问题描述

有一架天平和$n(1\le n\le 100)$个砝码，问通过灵活的使用砝码，这个天平可以称出多少种不同的质量。

---

分析

步骤一：确定状态
步骤二：确定状态转移方程
步骤三：确定边界情况和初始条件
步骤四：确定计算顺序

步骤一：确定状态
以$dp[i][j]$表示有$i$个砝码时，能否称量出质量$j$，1表示可行，0表示不可行。
步骤二：确定状态转移方程
欲求$dp[i][j]$，已知在有$i-1$个砝码的条件下的所有称量情况，接下来就是求处理第$i$个砝码时的所可以得到的称量情况。
1.若不放该砝码，则$dp[i][j]=dp[i-1][j]$;
2.若放，则又有两种情况，于左或于右：
前提当然是$dp[i-1][j]$要存在。

if(dp[i-1][j]){
	dp[i][j+m[i]]=1;
	if(j-m[i]>0)dp[i][j-m[i]]=1;
}

步骤三：确定边界情况和初始条件
边界条件是无论多少砝码，都可以称量出质量$0$
步骤四：确定计算顺序
自上往下，自左往右。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
#define INF 99999999
int dp[105][N];
int a[N];
int n; 
int main(){
	cin>>n;
	dp[0][0]=1;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		dp[i][0]=1;
	}
	for(int i=1;i<=n;i++){
		for(int j=N-1;j>=0;j--){
			if(dp[i-1][j]){
				dp[i][j]=1;
				dp[i][j+a[i]]=1;
				dp[i][abs(j-a[i])]=1;
			}
		}
	}
	int ans=0;
	for(int i=0;i<N;i++){
		if(dp[n][i]){
			ans++;
			cout<<i<<endl;
		}
	}
	cout<<ans-1;
	return 0;
}
/*
3
1 4 6

10
*/

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fir(i, a, b) for (int i = (a); i <= (b); i++)
#define rif(i, a, b) for (int i = (a); i >= (b); i--)
const ll N=1e5+5;
const ll mod=1e9+7;
ll n,m,a[105][N];
int main(){
	cin>>n;
	fir(j,1,n){
		cin>>m;
		a[j][m]++;
		fir(i,1,N-1){
			if(a[j-1][i]){
				a[j][i]=1;
				a[j][i+m]=1;
				a[j][abs(i-m)]=1;
			}
		}
	}
	ll cnt=0;
	fir(i,1,N-1){
		if(a[n][i]){
			cnt++;
			//cout<<i<<" ";
		}
	}
	cout<<cnt;
}