社区讨论

求助WA问题

P5020[NOIP 2018 提高组] 货币系统参与者 3已保存回复 4

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
4 条
当前快照
1 份
快照标识符
@lo169ic7
此快照首次捕获于
2023/10/22 15:53
2 年前
此快照最后确认于
2023/11/02 15:28
2 年前
查看原帖
rt,链接
代码:
CPP
#include <bits/stdc++.h>
#define int long long

using namespace std;

const int MAXN = 105, MAXM = 25010;
int t, n, a[MAXN], dp[MAXM];

signed main(){
    cin >> t;
    // fstream fout;
    // fout.open("P5020测试点1.txt");
    while(t --){
        cin >> n;
        int ans = n;
        memset(a, 0, sizeof(a));
        for(int i = 1; i <= n; i ++) cin >> a[i];
        sort(a + 1, a + n + 1);
        bool vis[MAXN];
        for(int now = 2; now <= n; now ++){
            memset(dp, 0, sizeof(dp));
            for(int i = 1; i <= now - 1; i ++){
                if(vis[i]) continue;
                for(int j = a[i]; j <= a[now]; j ++){
                    dp[j] = max(dp[j], dp[j - a[i]] + a[i]);
                }
            }
            if(a[now] == dp[a[now]]){
                vis[now] = 1;
                ans --;
            }
        }
        cout << ans << endl;
    }
    return 0;
}
```cpp
已经下载过第一个测试点,在本地跑后和给出的输出一样。

回复

4 条回复,欢迎继续交流。

正在加载回复...