第十二届蓝桥杯省赛CC++ 研究生组-砝码称重

本文主要是介绍第十二届蓝桥杯省赛CC++ 研究生组-砝码称重，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

在这里插入图片描述

solution1（通过10%）

写了几种可能的组合方式，骗到一丢丢分数

#include<iostream>
#include<algorithm>
#include<map>
using namespace std;
int main(){int n, a[110], count = 0, sum[110] = {0};map<int, int> mp;scanf("%d", &n);for(int i = 0; i < n; i++){scanf("%d", a + i);if(i == 0) sum[i] = a[i];else sum[i] = a[i] + sum[i - 1];mp[a[i]] = 1;mp[sum[i]] = 1;} sort(a, a + n); for(int i = 1; i <= sum[n - 1]; i++){if(mp[i] == 1) continue;for(int j = n - 1; j >= 0; j --){for(int k = 0; k < j; k++){if(a[j] - a[k] == i){mp[i] = 1;continue;}}}if(!mp[i]){for(int j = n - 1; j>= 0; j--){for(int k = 0; k < j; k++){if(a[k] + a[j] == i){mp[i] = 1;continue;}}}}}printf("%d", mp.size());return 0;
}

solution2（动规）

#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 100010, N = 110;
int dp[N][maxn] = {0}, w[N];//dp[i][j]表示用前i个砝码，是否可以称出j克的重量 
int main(){int n, max = 0, count = 0;scanf("%d", &n);for(int i = 1; i <= n; i++){scanf("%d", w + i);max += w[i];}for(int i = 1; i <= n; i++){//依次计算前i个砝码能够称出的重量 for(int j = 1; j <= max; j++){//依次判断所有可能的重量是否能称出来 dp[i][j] = dp[i - 1][j];//用i个砝码能称出来的重量，i+1个肯定也能成if(dp[i][j] == 0){//i-1个不能称，看看加上第i个行不行//能称出的三种情况：1.刚好是第i个砝码本身重量  2.已经能称出来j+a[i]，第i个拿到对面 3.已经能称出abs(j-a[i])加上第i个 if(w[i] == j || (dp[i - 1][j + w[i]]) || (dp[i-1][abs(j - w[i])])) dp[i][j] = 1; } }}for(int j = 1; j <= max; j++)count += dp[n][j];printf("%d", count);return 0;
}