Northwestern European Regional Contest 2017-I题- Installing Apps题解

博观而约取，厚积而薄发。这篇文章主要讲述Northwestern European Regional Contest 2017-I题- Installing Apps题解相关的知识，希望能为你提供帮助。
一、题意
有一个手机，容量为$C$，网上有$N$个app，每个app有个安装包大小$d_i$，有个安装后的占用空间大小$s_i$，安装app是瞬间完成的，即app的占用空间可以瞬间由$d_i$变成$s_i$，而不需要其他多余的空间。问这个手机最多可以安装多少个app，输出最多可以安装的app数量和安装顺序。
二、思路
很显然的$dp$。按照$max(d,s)-s$从大到小排序。$dp[i][j]$表示在前$i$个app中，占用空间不超过$j$的条件下最多可以安装的app的数量。那么，有如下递推式：
枚举$1 le i le N,0 le j le C$，如果$j< s_i$，$dp[i][j]=dp[i-1][j]$；
如果$j ge s_i且C-(j-s_i) ge d_i$，$dp[i][j]=max(dp[i-1][j],dp[i-1][j-s_i]+1)$；
初始状态，全部的$dp$都是$0$。
然后，在状态转移的时候，需要记录选择的路径。
三、注意点
1、“ 如果$j ge s_i且C-(j-s_i) ge d_i$” ，意思是，如果$j ge s_i$且选择当前这个app之前剩余空间大于当前这个app的安装包大小，那么就可以安装这个app。
2、最后的答案不一定是$dp[N][C]$，而是$max{dp[N][j]|0 le j le C}$。
3、这题其实就是01背包模型，记录路径的方案和01背包一样。
4、切记：记录路径时，用额外数组的方式最靠谱。
四、代码

#include< bits/stdc++.h> using namespace std; struct app { int d, s, id; } p[510]; bool cmp(app a1, app a2) { return max(a1.d, a1.s) - a1.s > max(a2.d, a2.s) - a2.s; } int N, C, dp[510][10010], ans[510], acnt; bool path[510][10010]; int main() { scanf("%d%d", & N, & C); for(int i = 1; i < = N; ++i)scanf("%d%d", & p[i].d, & p[i].s), p[i].id = i; for(int i = 0; i < = N; ++i) { for(int j = 0; j < = C; ++j)dp[i][j] = 0; } sort(p + 1, p + N + 1, cmp); for(int i = 1; i < = N; ++i) { for(int j = 0; j < = C; ++j) { dp[i][j] = dp[i - 1][j]; if(j > = p[i].s) { int last = j - p[i].s; if(C - last > = p[i].d) { if(dp[i][j] < dp[i - 1][last] + 1) { dp[i][j] = dp[i - 1][last] + 1; path[i][j] = 1; } } } } } int V, aa = 0; for(int j = C; j > = 0; --j) { if(aa < dp[N][j]) { aa = dp[N][j], V = j; } } for(int i = N, j = V; i > 0; --i) { if(path[i][j]) { ans[++acnt] = p[i].id; j -= p[i].s; } } reverse(ans + 1, ans + acnt + 1); printf("%d ", acnt); for(int i = 1; i < = acnt; ++i)printf("%d ", ans[i]); return 0; } /* 3 4 2 1 3 2 3 3 */

【Northwestern European Regional Contest 2017-I题- Installing Apps题解】