洛谷 P2340 USACO03FALL Cow Exhibition G

url: https://www.luogu.com.cn/problem/P2340

tag:
动态规划,背包,USACO, 2003

思路:
可以转化为01背包问题来做,因为每个奶牛都只有选和不选两种状态。对于背包问题,需要考虑三个属性,一个是背包容量,一个是体积,还有一个是价值。在这道题中,iq和eq是等价的属性,所以可以一个当作体积,另外一个当作价值。关于背包容量,这道题没有显式的提出,不过我们可以用数据范围的最大值作为背包容量的最大值。因为iq和eq都是有正有负,所以就可以选择将数组向右扩大400000.因为转移方程是 f[j] = max(f[j], f[j - c[i].iq] + c[i].eq) 二维转变为一维。当是负数的时候,实际上 j - c[i].iq 是增大的,为了避免更新的对未更新的产生影响,所以需要变成从小到大遍历。

代码:

  1. #include <iostream>
  2. #include <cstring>
  3. #include <cstdio>
  4. #include <algorithm>
  5. using namespace std;
  6. const int N = 440;
  7. struct cow {
  8. int iq, eq;
  9. }c[N];
  10. int f[N * 1000 * 2];
  11. int n;
  12. int res;
  13. int main()
  14. {
  15. cin >> n;
  16. for (int i = 1; i <= n; i ++)
  17. {
  18. cin >> c[i].iq >> c[i].eq;
  19. }
  20. memset(f,-0x3f ,sizeof f);
  21. f[400000] = 0;
  22. for (int i = 1; i <= n; i ++)
  23. {
  24. if (c[i].iq >= 0)
  25. {
  26. for (int j = 800000; j >= c[i].iq; j --)
  27. {
  28. f[j] = max(f[j], f[j - c[i].iq] + c[i].eq);
  29. }
  30. }
  31. else
  32. {
  33. for (int j = 0; j <= 800000 + c[i].iq; j ++)
  34. {
  35. f[j] = max(f[j], f[j - c[i].iq] + c[i].eq);
  36. }
  37. }
  38. }
  39. for (int i = 400000; i <= 800000; i ++)
  40. {
  41. if (f[i] >= 0)
  42. res = max(res, f[i] + i - 400000);
  43. }
  44. cout << res << endl;
  45. return 0;
  46. }
添加新评论