社区讨论
求助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 条回复,欢迎继续交流。
正在加载回复...