不过不得不说，liu_runda确实很强呢。

Table of Contents

  1. Overview
  2. BZOJ 1334 Elect
    1. Description
    2. Solution
  3. BZOJ 2287 消失之物
    1. Description
    2. Solution
  4. BZOJ 2794 Cloakroom
    1. Description
    2. Solution
  5. BZOJ 1190 HNOI2007 梦幻岛宝珠
    1. Description
    2. Solution

Overview

一种新的思路, 线性DP是在找合理的拓扑序.

同时DP的思路要灵活. 这是一些题目.

BZOJ 1334 Elect

Description

$N$个政党要组成一个联合内阁，每个党都有自己的席位数. 现在希望你找出一种方案，你选中的党的席位数要大于

总数的一半，并且联合内阁的席位数越多越好. 对于一个联合内阁，如果某个政党退出后，其它党的席位仍大于总

数的一半，则这个政党被称为是多余的，这是不允许的.

Solution

需要使去掉一个政党后, 答案小于总数的一半, 如果直接做的话, 我们不能确定减掉最小的是否符合要求, 不妨排个序.

那么对于每个物品, 在对她DP时的体积上限就是 $\frac{sum}{2} + a_i$.

然后我们做一个可达DP, 更新答案就好了.

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int maxn = 305;
const int maxm = 100005;

int n, a[maxn], s, ans;
bool f[maxm];

bool cmp(int a, int b) {
  return a > b;
}

int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) scanf("%d", &a[i]), s += a[i];
  sort(a + 1, a + 1 + n, cmp);

  f[0] = true;
  for (int i = 1; i <= n; ++i) {
    for (int j = s / 2 + a[i]; j >= a[i]; --j) {
      f[j] |= f[j - a[i]];
      if (f[j]) ans = max(ans, j);
    }
  }
  printf("%d\n", ans);
  return 0;
}

BZOJ 2287 消失之物

Description

有$n$个物品, 体积上限为$m$, 计算去掉每个物品$i$, 装满体积上限为$[1,m]$的背包的方案数的最后一位.

Solution

一开始以为是做一遍前缀DP, 做一遍后缀DP, 然后把两边合并起来, 但这样其实是$O(nm^2)$的.

首先做完一遍DP. 考虑容斥一下, 如果当前枚举的体积$< a_i$, 那么$i$一定不在背包里, 直接复制答案.

如果$\ge a_i$, 那么答案就是总的方案数减去使用了$i$的方案数, 使用了$i$代表用其他物品填满$j - a_i$, 这个答案是已经求出的, 即$ans_{i,j-a_i}$.

补集转化的思路, 在正常DP行不通时经常用到. 要加以注意.

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
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>

using namespace std;

const int maxn = 2005;

int n, m, a[maxn], f[maxn];
int ans[maxn][maxn];

int main() {
  scanf("%d%d", &n, &m);
  f[0] = 1;
  for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
  for (int i = 1; i <= n; ++i)
    for (int j = m; j >= a[i]; --j)
      f[j] = (f[j] + f[j - a[i]]) % 10;
  for (int i = 1; i <= n; ++i) {
    ans[i][0] = 1;
    for (int j = 1; j <= m; ++j) {
      if (j < a[i]) ans[i][j] = f[j];
      else ans[i][j] = (f[j] - ans[i][j - a[i]] + 10) % 10;
    }
  }
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j)
      printf("%d",ans[i][j]);
    putchar('\n');
  } 
  return 0;
}

BZOJ 2794 Cloakroom

Description

有$n$件物品，每件物品有三个属性$a[i], b[i], c[i] (a[i]<b[i])$。

再给出$q$个询问，每个询问由非负整数$m, k, s$组成，问是否能够选出某些物品使得：

对于每个选的物品$i$，满足$a[i] \le m$且$b[i]>m+s$。

所有选出物品的$c[i]$的和正好是$k$。

Solution

每次都做一遍DP太慢了, 考虑将问题离线, 按顺序用一遍背包解决所有问题.

这样就将问题转化成了, 在装满$k$的情况下, 最小的$b_i$大于一个值.

这是可以DP的, 我们只要求出每次转移时选择该物品的答案较小值, 并更新答案为选或不选的较大值即可.

每次完成询问时检查$f_k$是否大于要求的值即可.

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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>

using namespace std;

const int maxn = 1005;
const int maxq = 1e+6 + 5;
const int maxv = 1e+5 + 5;

inline int rd() {
  register int x = 0; register char c = getchar();
  while (!isdigit(c)) c = getchar();
  while (isdigit(c)) x = x * 10 + (c ^ 48), c = getchar();
  return x;
}

class obj {
 public:
  int a, b, c;
  bool operator < (const obj &rhs) const {
    return a < rhs.a;
  }
};
class query {
 public:
  int M, k, s, id;
  bool operator < (const query &rhs) const {
    return M < rhs.M;
  }
};
int n, m;
obj t[maxn]; query q[maxq];
int ans[maxq], f[maxv];

int main() {
  n = rd();
  for (int i = 1; i <= n; ++i) //t[i].init();
    t[i].c = rd(), t[i].a = rd(), t[i].b = rd();
  m = rd();
  for (int i = 1; i <= m; ++i) //q[i].init(i);
    q[i].M = rd(), q[i].k = rd(), q[i].s = rd(), q[i].id = i;
  sort(t + 1, t + 1 + n);
  sort(q + 1, q + 1 + m);
  f[0] = 0x3f3f3f3f;
  int ptr = 1;
  for (int i = 1; i <= m; ++i) {
    while (t[ptr].a <= q[i].M && ptr <= n) {
      for (int j = 100000; j >= t[ptr].c; --j)
    f[j] = max(f[j], min(f[j - t[ptr].c], t[ptr].b));
      ptr++;
    }
    // printf("%d %d\n", i, f[q[i].k]);
    if (f[q[i].k] > q[i].M + q[i].s) ans[q[i].id] = 1;
  }
  for (int i = 1; i <= m; ++i) {
    if (ans[i]) puts("TAK");
    else puts("NIE");
  }
  return 0;
}

BZOJ 1190 HNOI2007 梦幻岛宝珠

Description

给你$N$颗宝石，每颗宝石都有重量和价值。要你从这些宝石中选取一些宝石，保证总重量不超过$W$，且总价值最大，并输出最大的总价值。

$ N \le 100, W \le 2^30$,并且保证每颗宝石的重量符合$a \times 2^b（a \le 10, b \le 30)$.

Solution

看起来就是一个背包, 但是无论是体积还是背包限制都太大了, 既然题目说满足$a \times 2^b$的性质, 我们就可以从这里入手, 由于$2$的同次幂是可以转移的, 我们只要考虑如何在相邻幂之间做系数的转化.

可以考虑将高于当前二进制位的数都看作系数， 那么当二进制位继续右移时，系数将变为$ \big\lceil \small{fac - [w\, \&\, (1 << i)]} \big\rceil$ .

然后就可以做了.

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
42
43
44
45
46
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>

using namespace std;

typedef long long ll;

const int maxn = 105;

struct stu {
  int b, c, v;
  bool operator < (const stu &rhs) const {
    return b < rhs.b;
  }
}a[maxn];
int n, w;
int f[32][1005];

int main() {
  while (scanf("%d%d", &n, &w) &&
	 n != -1 && w != -1) {
    memset(a, 0, sizeof a); memset(f, 0, sizeof f);
    for (int i = 1; i <= n; ++i) {
      scanf("%d%d", &a[i].c, &a[i].v);
      while (!(a[i].c & 1)) a[i].c >>= 1, a[i].b++;
    }
    sort(a + 1, a + 1 + n);
    int ptr = 1, fac = 0;
    for (int i = 0; i <= 30; ++i) {
      while (ptr <= n && a[ptr].b == i) {
	fac = min(fac + a[ptr].c, w >> i);
	for (int j = fac; j >= a[ptr].c; --j)
	  f[i][j] = max(f[i][j], f[i][j - a[ptr].c] + a[ptr].v);
	++ptr;
      }
      for (int j = 0; j <= fac; ++j)
	f[i + 1][(j - ((w & (1 << i))?1:0) + 1) >> 1] =
	  max(f[i + 1][(j - ((w & (1 << i))?1:0) + 1) >> 1], f[i][j]);
      fac = (fac - ((w & (1 << i))?1:0) + 1) >> 1;
    }
    printf("%d\n", f[31][0]);
  }
  return 0;
}