P1441 砝码称重

时间:2023-03-09 23:15:20
P1441 砝码称重

题目描述

现有n个砝码,重量分别为a1,a2,a3,……,an,在去掉m个砝码后,问最多能称量出多少不同的重量(不包括0)。

输入输出格式

输入格式:

输入文件weight.in的第1行为有两个整数n和m,用空格分隔

第2行有n个正整数a1,a2,a3,……,an,表示每个砝码的重量。

输出格式:

输出文件weight.out仅包括1个整数,为最多能称量出的重量。

输入输出样例

输入样例#1: 复制
3 1
1 2 2
输出样例#1: 复制
3

说明

【样例说明】

在去掉一个重量为2的砝码后,能称量出1,2,3共3种重量。

【数据规模】

对于20%的数据,m=0;

对于50%的数据,m≤1;

对于50%的数据,n≤10;

对于100%的数据,n≤20,m≤4,m<n,ai≤100。

做求方案个数的题目,一般都是bool的dp传递

这题先dfs出每种删m个砝码后的状态,交给Dp处理

(bool) dp[i][j]:前i个砝码,是否可达重量为j

显然可以压成一维,第二层for记得逆序

#include <bits/stdc++.h>
using namespace std;
#define maxn 100000
typedef long long ll;
#define inf 2147483647
#define ri register int int n, m;
int a[];
bool dp[maxn];
bool flag[maxn];
int ans = ; void work() {
int sum = ;
memset(dp, , sizeof(dp));
int tot = ;
dp[] = ;
for (int i = ; i <= n; i++) {
if (flag[i])
continue;
tot += a[i];
for (int j = tot; j >= a[i]; j--)
if (!dp[j] && dp[j - a[i]]) {
dp[j] = true;
sum++;
}
}
ans = max(ans, sum);
} void dfs(int cur, int cnt) {
if (cnt > m)
return;
if (cur == n + ) {
if (cnt == m)
work();
return;
}
dfs(cur + , cnt);
flag[cur] = true;
dfs(cur + , cnt + );
flag[cur] = false;
} int main() {
ios::sync_with_stdio(false);
// freopen("test.txt", "r", stdin);
// freopen("outout.txt","w",stdout);
cin >> n >> m;
for (int i = ; i <= n; i++)
cin >> a[i];
dfs(, ); cout << ans; return ;
}