ZOJ 3956

发表于 |

题目

有$N$门课程，第$i$门课程有$2$个属性$H_i$和$C_i$ 。从$N$门课程中选择$m(m\leq0)$门课程,记为第$x_1,x_2,\cdots,x_m$门课程，使$a^2−a\times b−b^2$取最大值。

其中：$a:=\sum{i=1}^mH\{x_i} \quad b:=\sum{i=1}^mC\{x_i}$

数据范围

$1\leq N \leq 500 \quad 1 \leq H_i \leq 10000 \quad 1 \leq C_i \leq 100$

做法

感觉是DP，但是定义$dp[i]:=$前$i$门中所能得到的最大值，推了一下发现并不满足最优性原理，也不是多段决策。

注意到，$C$的范围很小。考虑将$C$也当作状态的一维。

当$b$固定时，要最大化的函数记为$f(x)=x^2−b\times x−b^2$是关于$x$的二次函数，且对称轴$>0$ 。而$f(0)=−b^2<0$，所以函数最大值在$0$或者$x$的最大值处取得。于是，问题规约为求$b$固定时$x$的最大值。

我们以$C$为重量，$H$为价值，做一个背包，即可求出$b$为定值时$x$的最大值。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
typedef long long ll;
const int MAX_N = 505, MAX_W = 105 * 505;
int N, W;
ll dp[MAX_W];
int w[MAX_N], v[MAX_N];
inline ll f(int x, int c)
{
  return 1LL * x * x - 1LL * x * c - 1LL * c * c;
}
ll solve()
{
  memset(dp, 0, sizeof dp);
  for (int i = 0; i < N; ++i) {
    for (int j = W; j >= w[i]; --j) {
      dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
    }
  }
  ll ans = 0;
  for (int j = 0; j <= W; ++j) {
    ans = max(ans, f(dp[j], j));
  }
  return ans;
}
int main()
{
  int T; cin >> T;
  while (T--) {
    scanf("%d", &N);
    W = 0;
    for (int i = 0; i < N; ++i) {
      scanf("%d%d", &v[i], &w[i]);
      W += w[i];
    }
    cout << solve() << endl;
  }
  return 0;
}

注意

乘法会超过int的范围。