ZOJ - 3956 Course Selection System——01背包变形

ZOJ - 3956 Course Selection System——01背包变形

There are n courses in the course selection system of Marjar University. The i-th course is described by two values: happiness Hi and credit Ci. If a student selects m courses x1, x2, ..., xm, then his comfort level of the semester can be defined as follows:

Edward, a student in Marjar University, wants to select some courses (also he can select no courses, then his comfort level is 0) to maximize his comfort level. Can you help him?

题意：有n个物品，每个物品有两个价值hi与ci，每个物品可以选或者不选，求可获得的最大价值和，价值和的计算方式题目中已经给出

思路：把价值和存入空间，然后dp求解哪些状态是可行的，最终遍历一下价值和，找出最大的可行状态即可，可惜价值和太大了，数组根本存不下。

然而我们发现虽然价值之和存不下，但是c的总和不过50000，是可以存下的，因此可以从c的总和入手，因为对于一个c的总和sumc，若想让价值和最大，那么sumh应该最大（如果不明白为什么就先默认，一会儿会解释），所以我们定义dp【i】【j】表示选到第i个物品时，sumc为j的最大sumh，注意一定保证dp【i】【j】是一个可行状态（也就是说sumc一定可以被题目中的数据凑出来），状态转移方程为dp【i】【j】=max（dp【i-1】【j】，dp【i-1】【j-c【i】】+h【i】），一定要保证dp【i-1】【j-c【i】】是一个可行状态，这样dp【i】【j】才是一个可行状态。

最终结果就是遍历一遍所有可行状态，求dp【i】*dp【i】-dp【i】*i-i*i的最大值，注意用longlong

至于对于一个特定的sumc，为什么要选最大的sumh，根据题目中的式子画出图像就可以看出，y大于0、x大于0的部分

是单调递增的，而y小于0或者x小于0的部分是没有意义的，特别注意没有y大于0、x大于0单调递减的情况

#include #include #include #include using namespace std;const int INF = 0x3f3f3f3f;const int maxn = 5e4+5;int h[505], c[505], dp[maxn];int main() { int T, n; scanf("%d", &T); for (int kase = 1; kase <= T; kase++) { scanf("%d", &n); int sum = 0; for (int i = 1; i <= n; i++) { scanf("%d %d", &h[i], &c[i]); sum += c[i]; } for (int i = 1; i <= sum; i++) dp[i] = -INF; dp[0] = 0; for (int i = 1; i <= n; i++) { for (int j = sum; j >= c[i]; j--) { if (dp[j-c[i]] == -INF) continue; dp[j] = max(dp[j], dp[j-c[i]] + h[i]); } } long long ans = 0; for (int i = 1; i <= sum; i++) { if (dp[i] == -INF) continue; ans = max(ans, (long long)dp[i]*dp[i]-(long long)dp[i]*i-(long long)i*i); } printf("%lld\n", ans); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。