【蓝桥杯·dp问题】砝码称重

此题易联想到使用动态规划解决，dp[i][j] 状态表示是否存在前i个砝码中选取重量为j的方案。

砝码重量分三种情况：

1. 砝码本身的重量（即一个砝码就可以表示的重量）

2. 放在同侧

3. 放在异侧

注意重量为0的情况不记作方案数。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;

const int N=110;
const int M=1e5+10;
int d[N][M];
int w[N];
int n,summ,cnt;

int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>w[i];
		summ+=w[i];
	}//for
	
	//cout<<summ<<endl;
	
	for(int i=1;i<=n;i++){
		for(int j=1;j<=summ;j++){
			d[i][j]=d[i-1][j];
			if(d[i][j]==0){
				if(j==w[i]) d[i][j]=1; //单个砝码表示的重量 
				if(d[i-1][j+w[i]]) d[i][j]=1; //放在异侧的情况 （减去当前砝码重量符合要求） 
				if(d[i-1][abs(j-w[i])]) d[i][j]=1; //放在同侧的情况 （加上当前砝码重量符合要求） 
				
				}
			
		}//for2
		
	}//for1
	
	
	for(int j=0;j<=summ;j++){
		if(d[n][j]==1) cnt++;
	}//for2
	
	cout<<cnt<<endl;
	
	return 0;
}//main