[数据结构与算法]【蓝桥杯】【第12届省赛B题 砝码称重】DP

题目链接：

题意：

给你一堆砝码，问能称出来多少个数量。比如1 和 3就能称出来1 2 3 4，因为是用天平测的，所以说可以放在左边也可以放在右边，看一下题面也可以理解

分析：

当时考试的时候我记得是直接暴搜，赛后查了一下是40分，看一下暴搜的代码吧：

#include<iostream>
#include<map>
#include<cstdlib>
using namespace std;
typedef long long LL;
const int N = 100;
map<LL,int> mp;
LL ans,x[N],n;
void dfs(int u,int l,int r){
    if(mp[abs(l-r)] == 0){
        mp[abs(l-r)]++;
        ans++;
    }
    if(u > n) return;
    dfs(u+1,l+x[u],r);
    dfs(u+1,l,r+x[u]);
    dfs(u+1,l,r);
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>x[i];
    dfs(1,0,0);
    cout<<ans-1<<endl;
    return 0;
}

AC代码：

就是DP的思路，mp[i][j]表示从前 i 个砝码中选，j 这个数是否能被表示出来，那么每种情况的状态转移就是三个情况：
1、第一种就是从前 i - 1 个砝码中能表示出 j - x[i] 这个数，x[i]表示的是第 i 个砝码的重量，那么就可以表示出这个数。
2、第二种就是从前 i - 1 个砝码中能表示出 j + x[i] 这个数，也可以表示出 j 这个数。
3、第三种就是从前 i - 1 个砝码中能表示出 x[i] - j 这个数 ，也可以表示出这个数。
对以上三种情况，如果能表示出来这个数，那么答案就+1，这里空间优化用的是滚动数组，下面请看代码 （PS：这个题在蓝桥杯官网是AC了的，但是在ACWing上WA在了第六个点，我不理解~） ：

#include<iostream>
#include<unordered_map>
using namespace std;
typedef long long LL;
const int N =100010;
LL mp[2][N];
LL ans,n,x[110];
int maxx[N];
int main(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>x[i],maxx[i] = maxx[i-1] + x[i];
    for(int i=1;i<=n;i++){
        mp[(i%2)^1][0]++;
        for(int j=0;j<=maxx[i];j++){
            if(j >= x[i] && !mp[(i%2)^1][j] && mp[(i%2)^1][j-x[i]]){
                mp[(i%2)&1][j]++;
                ans++;
            }
            else if(mp[(i%2)^1][j+x[i]] && !mp[(i%2)^1][j]){
                mp[(i%2)&1][j]++;
                ans++;
            }
            else if(x[i]-j >= 0 && mp[(i%2)^1][x[i]-j] && !mp[(i%2)^1][j]){
                mp[(i%2)&1][j]++;
                ans++;
            }
            if(mp[(i%2)^1][j]) mp[(i%2)&1][j]++;
        }
    }
    cout<<ans<<endl;
    return 0;
}