【每日一题】小M和天平 题解

Description

给一个天平和一堆已知重量的石头，判断目标重量能否搭配出来。

Solution

假设石头放左边贡献是 , 放右边是
根据数据，最大的重量只能是
不妨令 为使用第 个石头的时候能否到达重量为 的状态
显然有

• 不取
• 放在右边
• 放在左边

最后查询的时候检查是否能到达状态即可
时间复杂度

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e5 + 5;
int a[105];
bool vis[10505];
bool dp[105][10505];
int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int n; 
    while(cin >> n) {
        memset(dp, false, sizeof(dp));
        memset(vis, false, sizeof(vis));
        for(int i = 1; i <= n; i++) {
            cin >> a[i];
        }    
        dp[0][0] = true;
        for(int i = 1; i <= n; i++) {
            for(int j = 0; j <= 1e4; j++) {
                dp[i][j] |= dp[i - 1][j];
                dp[i][j] |= dp[i - 1][abs(j - a[i])];
                dp[i][j] |= dp[i - 1][j + a[i]];
                if(dp[i][j]) {
                    vis[j] = true;
                }
            }
        }
        int m; cin >> m;
        while(m--) {
            int x; cin >> x;
            if(x > 1e4) {
                cout << "NO\n";
            } else {
                if(vis[x]) {
                    cout << "YES\n";
                } else {
                    cout << "NO\n";
                }
            }
        }
    }
    return 0;
}