【蓝桥杯】2021 省赛 c++ A组真题砝码称重

【蓝桥杯】2021 省赛 c++ A组真题砝码称重,第1张

你有一架天平和N个砝码,这N个砝码重量依次是W1,W2,……,WN请你计算一共可以称出多少种不同的重量?
注意砝码可以放在天平两边。


 【样例输入】
3
1 4 6
【样例输出】
10

思路:动态规划题,将每个砝码分为三个状态,+w,0,-w,然后利用set容器的唯一性遍历每一个砝码的状态,set中初始状态只有0,然后与砝码1三个状态相加得到状态2,然后逐一遍历。


注意:为了简化程序,每次加入相加的值的绝对值即可。


代码如下:

#include
#include
#include
#include
#include
using namespace std;
int main()
{
int n;
cin>>n;
int b[3][100];
int a[100],c[1000];
    for(int i=0;i         {
            cin>>a[i];
            b[0][i]=a[i];
            b[1][i]=0;
            b[2][i]=-a[i];
        }
    set m;
    set h;
    m.insert(0);
    int ca=0;
for(int i=0;i {
    for(int j=0;j<3;j++)
    {
        set::iterator it=m.begin();
        for(;it!=m.end();it++)
        {
            h.insert(abs(*it+b[j][i]));
        }

    }
    swap(m,h);
        h.clear();
}
set::iterator it=m.begin();
        for(;it!=m.end();it++)
        {
            if(*it>0)
            ca++;
        }
cout<     return 0;
}
 

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/langs/563244.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-04-02
下一篇 2022-04-02

发表评论

登录后才能评论

评论列表(0条)

保存