【蓝桥杯】试题历届真题砝码称重【第十二届】【省赛】【研究生组】

wzy1999

March 29, 2022

1120 views

1093 words

![](https://cdn.jsdelivr.net/gh/Friends-A/img@main/16485586302421648558629472.png)
![](https://cdn.jsdelivr.net/gh/Friends-A/img@main/16485586523141648558652280.png)

## 暴力50分写法

分成放左边，不放，放右边三种状态，暴力枚举

```cpp
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define ms(a,b) memset(a,b,sizeof(a))
const int inf=0x3f3f3f3f;
const ll INF=0x3f3f3f3f3f3f3f3f;
const int maxn=1e6+10;
const int mod=1e9+7;
const int maxm=1e3+10;
using namespace std;
int a[maxn];
int ans=0;
map<int,int>mp;
void dfs(int l,int r,int i,int n)
{
    if(!mp[abs(l-r)])
    {
        ans++;
        mp[abs(l-r)]=1;
    }
    if(i==n)
        return;
    dfs(l,r,i+1,n);
    dfs(l+a[i],r,i+1,n);
    dfs(l,r+a[i],i+1,n);
}
int main(int argc, char const *argv[])
{
    // #ifndef ONLINE_JUDGE
    //     freopen("in.txt", "r", stdin);
    //     freopen("out.txt", "w", stdout);
    //     srand((unsigned int)time(NULL));
    // #endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>a[i];
    mp[0]=1;
    dfs(0,0,0,n);
    cout<<ans<<endl;
    // #ifndef ONLINE_JUDGE
    //     cerr<<"Time elapsed: "<<1.0*clock()/CLOCKS_PER_SEC<<" s."<<endl;
    // #endif
    return 0;
}
```

## 满分DP写法

$dp[i][j]$表示前$i$个砝码是否有重量为$j$的组合，时间复杂度为$O(n\times \sum w_i)$

```cpp
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define ms(a,b) memset(a,b,sizeof(a))
const int inf=0x3f3f3f3f;
const ll INF=0x3f3f3f3f3f3f3f3f;
const int maxn=1e6+10;
const int mod=1e9+7;
const int maxm=1e3+10;
using namespace std;
bool dp[110][maxn];
int a[maxn];
int main(int argc, char const *argv[])
{
    // #ifndef ONLINE_JUDGE
        // freopen("in.txt", "r", stdin);
        // freopen("out.txt", "w", stdout);
    //     srand((unsigned int)time(NULL));
    // #endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin>>n;
    int sum=0;
    for(int i=0;i<n;i++)
        cin>>a[i],sum+=a[i];
    dp[0][a[0]]=1;
    for(int i=1;i<n;i++)
    {
        for(int j=1;j<=sum;j++)
            dp[i][j]=dp[i-1][j];
        dp[i][a[i]]=1;
        for(int j=1;j<=sum;j++)
        {
            if(dp[i-1][j])
            {
                dp[i][abs(j-a[i])]=1;
                dp[i][j+a[i]]=1;
            }
        }
    }
    int ans=0;
    for(int i=1;i<=sum;i++)
        ans+=dp[n-1][i];
    cout<<ans<<endl;
    // #ifndef ONLINE_JUDGE
    //     cerr<<"Time elapsed: "<<1.0*clock()/CLOCKS_PER_SEC<<" s."<<endl;
    // #endif
    return 0;
}
```

Last modification：March 29, 2022