sin bsp main truct vector 最优 pac name int
原题连接:http://codeforces.com/problemset/problem/864/E
题意:一个人想从大火中带走一些东西。每次他只能带一个,耗时ti ,价值为pi, 当总时间超过di时不能被带走。问他如何按顺序带走物品使价值总和最大。
思路:背包问题。分为取和不取两种情况1.dp[i][j]=max(dp[i-1][j], dp[i-1][j-t]+p), j<d;
2.dp[i][j]=max(dp[i-1][j], dp[i][j]);
AC代码:
- #include < iostream > #include < cstring > #include < cstdio > #include < algorithm > #include < vector > using namespace std;
- struct G {
- int t,
- d,
- v;
- int id;
- }
- g[105];
- int dp[105][2005];
- bool vis[105][2005];
- bool cmp(G a, G b) {
- return a.d < b.d;
- }
- int main() {
- int n,
- maxx = 0;
- scanf("%d", &n);
- memset(dp, 0, sizeof(dp));
- memset(vis, 0, sizeof(vis));
- for (int i = 1; i <= n; i++) {
- scanf("%d %d %d", &g[i].t, &g[i].d, &g[i].v);
- g[i].id = i;
- maxx = max(maxx, g[i].d);
- }
- sort(g + 1, g + n + 1, cmp);
- int b;
- for (int i = 1; i <= n; i++) {
- b = 0;
- for (int j = 0; j <= maxx; j++) {
- if (j >= g[i].t && j < g[i].d && dp[i - 1][j] < dp[i - 1][j - g[i].t] + g[i].v) {
- dp[i][j] = dp[i - 1][j - g[i].t] + g[i].v;
- vis[i][j] = 1;
- } else dp[i][j] = dp[i - 1][j];
- if (dp[i][j] >= dp[i][b]) b = j;
- }
- }
- printf("%d\n", dp[n][b]);
- vector < int > ans;
- for (int i = n; i; i--) { //反推,得到最优取法
- if (vis[i][b]) {
- ans.push_back(g[i].id);
- b -= g[i].t;
- }
- }
- printf("%d\n", ans.size());
- for (int i = ans.size() - 1; i >= 0; i--) printf("%d ", ans[i]);
- return 0;
- }
Codeforces 864E - Fire(dp)
来源: http://www.bubuko.com/infodetail-2328673.html