本文共 1200 字,大约阅读时间需要 4 分钟。
题目链接:
时间:1 秒 空间:512 MB现有n个砝码,重量分别为a1,a2,a3,……,an,在去掉m个砝码后,问最多能称量出多少不同的重量(不包括0)。
输入的第1行为有两个整数n和m,用空格分隔
第2行有n个正整数a1,a2,a3,……,an,表示每个砝码的重量。
输出仅包括1个整数,为最多能称量出的重量。
3 1
1 2 2
3
样例说明
在去掉一个重量为2的砝码后,能称量出1,2,3共3种重量。
数据规模
对于20%的数据,m=0;
对于50%的数据,m≤1; 对于50%的数据,n≤10; 对于100%的数据,n≤20,m≤4,m<n,ai≤100。
先DFS出哪些是留下的n-m个砝码,然后再跑01背包,找出最多的那一个。
Accepted Code:#includeusing namespace std;int n, m, max_ = 0;int s[25], v[25], vis[25], dp[2005];void edge() { int ans = 0; memset(dp, 0, sizeof(dp)); dp[0] = 1; for (int i = 0; i < n - m; i++) { for (int j = 2000; j >= v[i]; j--) { if (!dp[j] && dp[j - v[i]]) { ans++; dp[j] = 1; } } } if (ans > max_) max_ = ans;}void DFS(int k, int t) { if (k >= n - m) { if (k == n - m) edge(); return ; } for (int i = t; i < n; i++) { if (!vis[i]) { vis[i] = 1; v[k] = s[i]; DFS(k + 1, i); vis[i] = 0; } }}int main() { scanf("%d%d", &n, &m); for (int i = 0; i < n; i++) scanf("%d", s + i); DFS(0, 0); printf("%d\n", max_); return 0;}
转载地址:http://zqftf.baihongyu.com/