联考「联测缺颔(exam)」题解

根据题目中关于变量和关键变量的描述和模拟赛最多不超过 $m$ 个变量的描述，考虑背包DP。

我们定义以下状态：

  • $dp_i$ 表示变量数为 $i$ 的最多关键变量数。
  • $f_i$ 表示变量数最多为 $i$ 的最大答案。
Warning

关于 $dp$ 数组的求法和一般的背包DP有些许不同，$dp_i$ 要求的是正好 $i$ 个变量，否则在求答案时可能不准确。

综上，$dp$ 数组的求解代码：

1
2
3
4
5
6

for(int i = 1;i <= n;i++) {
  for(int j = a[i];j <= m;j++) {
    if(j - a[i] != 0 && dp[j - a[i]] == 0) continue;
    dp[j] = max(dp[j],dp[j - a[i]] + b[i]);
  }
}

对于 $f$ 数组，我们可以枚举最后一个题目的变量数，之后开心度通过二分求解。 $$ f_i = \max_{1\leq j \leq i}(f_{i-j}+getAns(j,dp_j)) $$ 其中 $getAns(a,b)$ 为二分求解开心度的函数，$a$ 为变量数，$b$ 为关键变量数。

最后的答案为 $f_m$ 。

代码

 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

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,m,k;
int p[105],v[105];
int a[8005],b[8005];
int dp[8005],f[8005];
int getAns(int a,int b) {
  int l = 0,r = k,mid;
  while(l < r) {
    mid = (l + r) / 2;
    if(100 * b <= a * p[mid]) r = mid;
    else l = mid + 1;
  }
  return v[l] * a;
}
signed main() {
  scanf("%lld%lld%lld",&n,&m,&k);
  for(int i = 1;i <= k;i++) scanf("%lld",p + i);
  for(int i = 1;i <= k;i++) scanf("%lld",v + i);
  for(int i = 1;i <= n;i++) scanf("%lld%lld",a + i,b + i);
  for(int i = 1;i <= n;i++) {
    for(int j = a[i];j <= m;j++) {
      if(j - a[i] != 0 && dp[j - a[i]] == 0) continue;
      dp[j] = max(dp[j],dp[j - a[i]] + b[i]);
    }
  }
  for(int i = 1;i <= m;i++) {
    for(int j = 1;j <= i;j++) {
      f[i] = max(f[i],f[i - j] + getAns(j,dp[j]));
    }
  }
  printf("%lld\n",f[m]);
  return 0;
}