文章

砝码称重(2021省赛)

砝码称重1.png砝码称重2.png

思路1 直接每种情况都遍历一遍,递归,超时了

//超时代码
#include<bits/stdc++.h>
using namespace std;
long long int n;
map<long long int ,long long int >mp;
long long int a[1001];
long long int s[1001];
long long int cnt=0;
long long int sum=0;
void dfs(long long int x,long long int i){//前i-1项总和,位置i 
    if(i==n+1){
        if(s[i-1]>0&&mp[s[i-1]]==0){
            cnt++;
            mp[s[i-1]]=1;
        }
        return ;
    }
    s[i]=s[i-1];//不放置
    dfs(s[i],i+1); 
    s[i]=s[i-1]+a[i];
    dfs(s[i],i+1);
    s[i]=s[i-1]-a[i]; 
    dfs(s[i],i+1);
    return ;
}
int main()
{
    long long int i;
    cin>>n;
    for(i=1;i<=n;i++){
        cin>>a[i];
    }
    dfs(0,1);
    cout<<cnt<<endl;
    return 0;
}
​

思路2 dp,利用dp数组每次考虑一件物品是否摆放和摆放位置,第i次循环中,dp[x]=1,表示截止到考虑前i个物品,重量x可以被称出,在此基础上对所有dp[x]=1实施dp[x+w]=1和dp[x-w]=1; 因为结果可能为负数,所以数组位置前移1e5个单位 注意:最后计算结果中,重量0不计入,每个结果都有一个相反数(现实情况就是砝码放的一样,然后左右盘子的东西交换,实际是一种情况),所以要(cnt-1)/2 下面代码优化二维数组为一维数组,优化了空间复杂度, AC代码

#include<bits/stdc++.h>
using namespace std;
long long int maxn=1e6+10;
long long int dp[1000010];
queue<long long int >q;
int main()
{
    long long int n,x,y,z,i,j,t,tem;
    cin>>n;
    dp[100000]=1;
    for(i=1;i<=n;i++){
        cin>>t;
        for(j=0;j<=300001;j++){
            if(dp[j]==1){
                q.push(j);
            }
        }
        while(q.empty()!=1){
            tem=q.front();
            dp[tem+t]=1;
            dp[tem-t]=1;
            q.pop();
        }
    }
    long long cnt=0;
    for(i=1;i<=300001;i++){
        if(dp[i]==1){
            cnt++;
        }
    }
    cout<<(cnt-1)/2<<endl;
    return 0;
}

原题链接

https://www.lanqiao.cn/problems/1447/learning/

License:  CC BY 4.0