首页 > 代码库 > B. Checkout Assistant 01背包变形
B. Checkout Assistant 01背包变形
http://codeforces.com/problemset/problem/19/B
对于每个物品,能偷多ti个,那么先让ti + 1, 表示选了这个东西后,其实就是选了ti + 1个了。那么只需要选出>=n个即可。
一开始的时候想不到ti + 1,一直不知道能多选ti个后,本来是选了多少个。
#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> const int maxn = 2e3 + 20; int w[maxn]; int val[maxn]; LL dp[2000 * 2000 + 20]; void work() { int n; cin >> n; int sum = 0; for (int i = 1; i <= n; ++i) { cin >> w[i] >> val[i]; w[i]++; w[i] = min(w[i], 2000); sum += w[i]; } for (int i = 0; i <= 2000 * 2000 - 2; ++i) { dp[i] = 1e17L; } dp[0] = 0; sum = min(4000, sum); for (int i = 1; i <= n; ++i) { for (int j = sum; j >= w[i]; --j) { dp[j] = min(dp[j], dp[j - w[i]] + val[i]); } } LL ans = 1e17L; for (int i = n; i <= sum; ++i) { ans = min(ans, dp[i]); } cout << ans << endl; } int main() { #ifdef local freopen("data.txt", "r", stdin); // freopen("data.txt", "w", stdout); #endif work(); return 0; }
写了一个超时的二维费用背包
dp[i][j]表示前n个数选出i个,有j个可以免费拿的情况。
直接超时。
#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> const int maxn = 2e3 + 20; LL dp[maxn][maxn]; int ti[maxn]; int cost[maxn]; void work() { int n; cin >> n; int sum = 0; for (int i = 1; i <= n; ++i) { cin >> ti[i] >> cost[i]; sum += ti[i]; } for (int i = 0; i <= 2000 + 2; ++i) { for (int j = 0; j <= 2000 + 2; ++j) { dp[i][j] = 1e17L; } } dp[0][0] = 0; sum = min(2000, sum); for (int i = 1; i <= n; ++i) { for (int j = i; j >= 1; --j) { for (int k = sum; k >= ti[i]; --k) { dp[j][k] = min(dp[j][k], dp[j - 1][k - ti[i]] + cost[i]); } } } LL ans = 1e17L; for (int i = 1; i <= n; ++i) { for (int j = sum; j >= 0; --j) { dp[i][j] = min(dp[i][j], dp[i][j + 1]); } } for (int i = 1; i <= n; ++i) { ans = min(ans, dp[i][n - i]); } cout << ans << endl; // cout << dp[3][5] << endl; } int main() { #ifdef local freopen("data.txt", "r", stdin); // freopen("data.txt", "w", stdout); #endif IOS; work(); return 0; }
B. Checkout Assistant 01背包变形
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。