noip模拟22

07-22-2021 约 1250 字预计阅读 3 分钟

T1 d

淦！不应该改代码嗷！我以为正解的思路不对会TLE然后打了个DP

我的错误DP思路：设f[i][j]为前i个矩形中删掉了j个矩形时的最大面积， $f[i][j] = max(f[i - 1][j - 1].a * f[i - 1][j - 1].b, min(f[i - 1][j].a, s[i].a) * min(f[i - 1][j].b, s[i].b)$

$f[i][i].a = inf f[i][i].b = inf f[i][i - 1] = s[i] f[i][0].a = min(f[i - 1][0].a, s[i].a) f[i][0].b = min(f[i - 1][0].b, s[i].b)$

然后？然后大样例88个里对了75个（85.22%）我发现好像n比较大(>500?)的都比答案小。求hack

11pts 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
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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93


#include <bits/stdc++.h>
#define For(i, l, r) for (int i = (l), i##end = (r); i <= i##end; ++i)
#define Fordown(i, r, l) for (int i = (r), i##end = (l); i >= i##end; --i)
#define Set(a, v) memset(a, v, sizeof(a))

using namespace std;
const int maxn = 1000010;

template <typename type>
type read() {
  type s = 0, f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    s = s * 10 + ch - '0';
    ch = getchar();
  }
  return s * f;
}
struct SQU {
  int a, b;
} s[maxn];
struct F {
  int a, b;
  long long area;
} f[10001][10001];
int n, m, T;
int main() {
  freopen("_input", "r", stdin);
  freopen("_output", "w", stdout);
  T = read<int>();
  while (T--) {
    n = read<int>();
    m = read<int>();
    For(i, 1, n) {
      s[i].a = read<int>();
      s[i].b = read<int>();
    }
    if (m == 0) {
      int mina = 0x3f3f3f3f, minb = 0x3f3f3f3f;
      For(i, 1, n) {
        mina = min(s[i].a, mina);
        minb = min(s[i].b, minb);
      }
      cout << 1ll * mina * minb << endl;
      continue;
    }
    // f[1][0].area = s[1].a * s[1].b;
    f[1][0].a = s[1].a;
    f[1][0].b = s[1].b;
    f[1][1].a = 0x1f1f1f1f;
    f[1][1].b = 0x1f1f1f1f;
    For(i, 2, n) {
      For(j, i, n) {
        f[i][j].a = 0x1f1f1f1f;
        f[i][j].b = 0x1f1f1f1f;
      }
      f[i][0].a = min(f[i - 1][0].a, s[i].a);
      f[i][0].b = min(f[i - 1][0].b, s[i].b);
      f[i][i - 1].a = s[i].a;
      f[i][i - 1].b = s[i].b;
    }

    For(i, 2, n) {
      For(j, 1, min(m, i - 1)) {
        if (1ll * f[i - 1][j - 1].a * 1ll * f[i - 1][j - 1].b >
            1ll * min(f[i - 1][j].a, s[i].a) * 1ll *
                min(f[i - 1][j].b, s[i].b)) {
          f[i][j].area = 1ll * f[i - 1][j - 1].a * 1ll * f[i - 1][j - 1].b;
          f[i][j].a = f[i - 1][j - 1].a;
          f[i][j].b = f[i - 1][j - 1].b;
        } else {
          f[i][j].area = 1ll * min(f[i - 1][j].a, s[i].a) * 1ll *
                         min(f[i - 1][j].b, s[i].b);
          f[i][j].a = min(f[i - 1][j].a, s[i].a);
          f[i][j].b = min(f[i - 1][j].b, s[i].b);
        }
      }
    }
    long long ans = 0;
    For(i, 1, m) {
      ans = max(ans, f[n][i].area);
      // cout << f[n][i].area << endl;
    }
    cout << ans << endl;
  }
  //大样例正确率高达85.227%
  return 0;
}

正确解法：真就先按a从大到小排序，从a小的中弹出去m个并标记，再按b从大到小排序，从未标记的数上选出最小的b的位置。接着往回压a，压一个a小的中较大的并取消它的标记，弹一个没被标记过的b（防止弹重）如果现在压进去的点的b小于现在的b，就不用动b的指针了

Accepted




 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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85


#include <bits/stdc++.h>
#define For(i, l, r) for (int i = (l), i##end = (r); i <= i##end; ++i)
#define Fordown(i, r, l) for (int i = (r), i##end = (l); i >= i##end; --i)
#define Set(a, v) memset(a, v, sizeof(a))

using namespace std;
const int maxn = 100010;

template <typename type>
type read() {
  type s = 0, f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    s = s * 10 + ch - '0';
    ch = getchar();
  }
  return s * f;
}

struct R {
  int a, b, id;
} rect[maxn], ma[maxn], mb[maxn];
bool cmpa(R x, R y) {
  if (x.a != y.a) return x.a < y.a;
  if (x.b != y.b) return x.b < y.b;
  return x.id < y.id;
}
bool cmpb(R x, R y) {
  if (x.b != y.b) return x.b < y.b;
  if (x.a != y.a) return x.a < y.a;
  return x.id < y.id;
}

struct S {
  int id, val;
};

int T, n, m;
bool vis[maxn];
int main() {
  // freopen("_input", "r", stdin);
  // freopen("_output", "w", stdout);
  T = read<int>();
  while (T--) {
    n = read<int>();
    m = read<int>();
    For(i, 1, n) {
      rect[i].a = read<int>();
      rect[i].b = read<int>();
      rect[i].id = i;
      ma[i] = mb[i] = rect[i];
    }
    int mina, minb;
    int bptr = 1;
    long long ans = 0;
    sort(ma + 1, ma + 1 + n, cmpa);
    For(i, 1, m) { vis[ma[i].id] = true; }
    sort(mb + 1, mb + 1 + n, cmpb);
    For(i, 1, n) {
      if (!vis[mb[i].id]) {
        minb = mb[i].b;
        bptr = i;
        break;
      }
    }
    ans += 1ll * ma[1 + m].a * mb[bptr].b;
    Fordown(i, m, 1) {
      vis[ma[i].id] = false;
      if (cmpb(ma[i], mb[bptr])) { //a.b<b.b覆盖掉了无需再动b
        ans = max(ans, 1ll * ma[1 + i].a * mb[bptr].b);
        continue;
      }
      bptr++;
      while (vis[mb[bptr].id]) {
        bptr++;
      }
      ans = max(ans, 1ll * ma[i].a * mb[bptr].b);
    }
    cout << ans << endl;
  }
}

目录

noip模拟22

T1 d