蓝桥杯2021年第十二届省赛真题-砝码称重

解题思路:

注意事项:

参考代码:

#include<iostream>

using namespace std;

const int N=1e5+10;

int w[110];

int dp[110][N];

//dp[i][j]表示前i个砝码中是否可以乘得重量为j  可以的话dp[i][j]为1  不可以得话dp[i][j]为0

//如果前i个可以称出j的重量的话   那么前i-1个会有三种情况

//1.前i-1就能秤出j的重量（即不用第i个砝码） 

//2.3是用第i个砝码的情况

//2.前i-1个砝码能秤出 j+w[i]的重量   那么将第i个物品放到右侧 便能称出j的重量 

//3.前i-1个砝码能秤出abs(j-w[i])的重量  那么将第i个物品放到天平左侧 便能称出j的质量 

int main()

{

int n;

int sum=0;

cin>>n;

for(int i=1;i<=n;i++)

{

cin>>w[i];

sum+=w[i];

}

dp[0][0]=1;

for(int i=1;i<=n;i++)

{

for(int j=0;j<=sum;j++)

{

dp[i][j]=dp[i-1][j]||dp[i-1][j+w[i]]||dp[i-1][abs(j-w[i])];

}

} 

int res=0;

for(int i=1;i<=sum;i++)//前n个法码中看看可以秤出多少个不同的质量 

if(dp[n][i]) res++;

cout<<res<<endl;

}