「CSP-S 2022」假期计划的一个简单随机化做法
Tsukimaru
·
·
个人记录
如果 A < B < C < D 就可以做到 O(n^2) DP。
当然肯定不能这样钦定，所以我们可以任意打乱编号顺序，然后跑一遍 DP。即，令 p = \{2, 3, 4, \ldots, n\}，每次打乱数列 p，然后钦定 a' < b' < c' < d'，取 A = p_{a'}, B = p_{b'}, C = p_{c'}, D = p_{d'}。
所以一次的正确率是 $\frac 1{12}$。跑 $T$ 次的正确率就是
$$1 - \left( 1 - \frac 1{12} \right)^T$$
有
$$1 - \left( 1 - \frac 1{12} \right)^{12} \approx 1 - \frac 1e \approx 63\%$$
因为常数相当小，所以保守估计 2s 内可以跑 $100$ 次以上（在洛谷上甚至能跑两三百次）。
$$1 - \left( 1 - \frac 1{12} \right)^{100} \approx 99.98\%$$
## Code
```cpp
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <ctime>
#define For(i, l, r) for (i = l; i <= r; i++)
#define Fo(i, n) For(i, 1, n)
#define Rof(i, r, l) for (i = r; i >= l; i--)
#define Ro(i, n) Rof(i, n, 1)
typedef long long int64;
const int N = 2500 + 10;
const int M = 20000 + 10;
const int64 NINF = -5e18;
int n, m, k;
int64 ans = NINF;
int pre[M], to[M], head[N], wcnt;
int64 a[N];
bool w[N][N];
int id[N];
int64 f[N][4]; // f[i][j] 表示最后一个选的点是 i，已经选了 (j + 1) 个点的最优答案
inline void chkmax(int64 &x, int64 y) { x = x > y ? x : y; }
inline void fix(int64 &x) { x = (x < 0) ? NINF : x; }
inline void addedge(int u, int v)
{
pre[++wcnt] = head[u];
head[u] = wcnt;
to[wcnt] = v;
}
inline void add2edge(int u, int v)
{
addedge(u, v);
addedge(v, u);
}
void bfs(int s)
{
static int dis[N];
static int q[N], ql, qr;
int i, u;
Fo(i, n) dis[i] = -1;
dis[s] = 0;
q[ql = qr = 1] = s;
while (ql <= qr)
{
u = q[ql++];
for (i = head[u]; i; i = pre[i])
if (dis[to[i]] == -1)
{
dis[to[i]] = dis[u] + 1;
if (dis[to[i]] < k)
q[++qr] = to[i];
}
}
Fo(i, n) w[s][i] = (dis[i] >= 0);
}
inline int randint(int l, int r)
{
return rand() % (r - l + 1) + l;
}
inline void random_shuffle(int *a, int n)
{
int i;
For(i, 2, n) std::swap(a[randint(1, i)], a[i]);
}
void test()
{
int i, j;
bool *vis;
Fo(i, n) id[i] = i;
random_shuffle(id + 1, n - 1);
For(i, 2, n)
{
f[i][0] = 0;
f[i][1] = f[i][2] = f[i][3] = NINF;
vis = w[id[i]];
Rof(j, i - 1, 2) if (vis[id[j]])
{
chkmax(f[i][1], f[j][0]);
chkmax(f[i][2], f[j][1]);
chkmax(f[i][3], f[j][2]);
}
f[i][0] += a[id[i]];
f[i][1] += a[id[i]];
f[i][2] += a[id[i]];
f[i][3] += a[id[i]];
if (!vis[1])
f[i][0] = f[i][3] = NINF;
fix(f[i][0]);
fix(f[i][1]);
fix(f[i][2]);
fix(f[i][3]);
ans = std::max(ans, f[i][3]);
}
}
int main()
{
int i, u, v;
int start = clock();
srand(time(NULL));
scanf("%d %d %d", &n, &m, &k);
k++;
For(i, 2, n) scanf("%lld", &a[i]);
Fo(i, m)
{
scanf("%d %d", &u, &v);
add2edge(u, v);
}
Fo(i, n) bfs(i);
Fo(i, 1000)
{
test();
if (double(clock() - start) / CLOCKS_PER_SEC >= 1.8)
break;
}
printf("%lld\n", ans);
return 0;
}
```