首页 > 代码库 > E. The Values You Can Make 背包,同时DP
E. The Values You Can Make 背包,同时DP
http://codeforces.com/problemset/problem/688/E
题目需要在n个数中找出一个集合,使得这个集合的和为val,然后问这些所有集合,能产生多少个不同的和值。
题解是直接两个同时dp,设dp[j][h]表示主集合的和为j,能否产生h这个数字。
把他们看作是两个集合,对于每个数,都可以放在第一个集合,或者放在第一个集合后,再放入第二个集合。
#include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <algorithm> #include <assert.h> #define IOS ios::sync_with_stdio(false) using namespace std; #define inf (0x3f3f3f3f) typedef long long int LL; #include <iostream> #include <sstream> #include <vector> #include <set> #include <map> #include <queue> #include <string> #include <bitset> const int maxn = 500 + 20; bool dp[maxn][maxn]; set<int>ans; void work() { int n, k; cin >> n >> k; dp[0][0] = true; for (int i = 1; i <= n; ++i) { int x; cin >> x; for (int j = k; j >= 0; --j) { for (int h = j; h >= 0; --h) { if (j >= x) { //第一个集合 dp[j][h] = dp[j][h] || dp[j - x][h]; } // if (h >= x) { // dp[j][h] = dp[j][h] || dp[j][h - x]; // } if (h >= x && j >= x) { dp[j][h] = dp[j][h] || dp[j - x][h - x]; } } } } // cout << dp[5][0] << endl; for (int i = 0; i <= k; ++i) { if (dp[k][i] == false) continue; ans.insert(i); } cout << ans.size() << endl; for (set<int> :: iterator it = ans.begin(); it != ans.end(); ++it) { cout << *it << " "; } } int main() { #ifdef local freopen("data.txt", "r", stdin); // freopen("data.txt", "w", stdout); #endif work(); return 0; }
E. The Values You Can Make 背包,同时DP
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。