DP题解

[P6772 [NOI2020] 美食家] (https://www.luogu.com.cn/problem/P6772)

ZAK解题思路

蒟蒻语

wtcl, 只会最简单的题目

这道题目与 [P6569 NOI Online #3 提高组]魔法值（民间数据） 类似, 都是倍增优化矩阵乘法。

蒟蒻解

首先观察数据, 看到 w**i≤5, 可以想到储存下前 5 天的状态, 从而推出现在的状态。

显然着这样是 O(n**wT) 的, 不可通过次题。

但是考虑到 n 很小, 可以使用矩阵乘法优化。然后按照图建立矩阵 a。大概是这样子的：

原来的数组（now表示转移结束后的状态）：

now−5	now−4	now−3	now−2	now−1

要变成：

now−4	now−3	now−2	now−1	now

转移矩阵 a :

0	0	0	0	w=5 的转移
S	0	0	0	w=4 的转移
0	S	0	0	w=3 的转移
0	0	S	0	w=2 的转移
0	0	0	S	w=1 的转移

S 表示单位矩阵

形如这样子的：

1	0	0
0	1	0
0	0	1

矩阵快速幂即可。时间复杂度为 O((n**w)3logT)

但是这只是没有美食节的情况, k=0。对于每次美食节, 可以先把答案算到美食节的时间 −1。然后对原来建立的矩阵进行矩阵快速幂, 时间复杂度 O(k(n**w)3log**T), 不可通过本题。

考虑继续优化。矩阵快速幂多次计算了一个矩阵的 2t 次方, 考虑优化调这个时间。倍增预处理出原矩阵的 2t 次方。这部分的代码：

void build() {btd[0] = a; // btd 是倍增矩阵。for(int i = 1; i <= 30; i++) btd[i] = btd[i - 1] * btd[i - 1]; // 利用2^{t-1}矩阵的信息处理出2^t的矩阵。
}

求值时拿原来的序列乘以需要乘的矩阵。那么这部分的代码是：

void get(ll *f, int b) {for(int i = 0; i <= 30; i++) if(b & (1 << i)) cf(f, btd[i]);// cf : 乘法， 代表数组(1*(nw)的矩阵)乘以矩阵
}

预处理时间复杂度是 (n**w3)logT, 而单次求值是 (n**w2)log**T, 求 m 次就是 m(n**w)2logT, 总时间复杂度是 (n**w3)logT+m(n**w)2logT, 可以通过本题。

// 这是一个很显然的递推
R(i,0,n)L(j,0,m) con[i][j]&&(nex[i][j]=max(j+1,nex[i][j+1]));

为了后面 A* 做准备，还可以求出一个 mnj 表示打到靶子 j 的剩余步数下限。

L(j,0,m)R(i,0,n) con[i][j]&&(mn[j]=min(mn[j],mn[nex[i][j]]+1));

然后就可以开始惊心动魄的 Dfs 了。

最直接的方法是先用 mnj 来剪枝 A* 一下，然后用 nexi,j 枚举下一个区间端点，用过的箭塔打个标记，匹配一个没用过的箭塔。

前文说过这是个二分图匹配，所以有个野蛮操作（二分图优化）：每次区间找好后，直接匈牙利匹配看看能不能匹配得到箭塔。

这个操作时间复杂度比起原来操作是不增的。

但是这有什么用呢？要配上另一个骚操作：逆序枚举下一个区间开始端点。

由于用了匈牙利后完美匹配概率变高，所以就可以尽早找到优的答案，进一步 A* 剪枝。

然后就结束了，时限 2s 的题跑得最慢的点 4ms，总时间 31ms。

注意 Dfs 回溯算法两个坑：回溯不彻底、回溯用了全局变量。

代码实现

点击查看代码

#include <bits/stdc++.h>
using namespace std;
int mn;
struct M {ll a[255][255];
} a;
M clear() {M res;for(int i = 1; i <= mn; i++) for(int j = 1; j <= mn; j++) res.a[i][j] = -inf;return res;
}
M operator * (M aa, M bb) {M res = clear();for(int i = 1; i <= mn; i++) for(int j = 1; j <= mn; j++) for(int k = 1; k <= mn; k++)res.a[i][j] = max(res.a[i][j], aa.a[i][k] + bb.a[k][j]);return res;
}
M btd[33];
void cf(ll *f, M b) {ll fz[255];for(int i = 1; i <= mn; i++) fz[i] = f[i], f[i] = -inf;for(int i = 1; i <= mn; i++) for(int j = 1; j <= mn; j++) f[i] = max(f[i], fz[j] + b.a[j][i]);
}
void get(ll *f, int b) {for(int i = 0; i <= 30; i++) if(b & (1 << i)) cf(f, btd[i]);
}
void build() {btd[0] = a;for(int i = 1; i <= 30; i++) btd[i] = btd[i - 1] * btd[i - 1];
}
struct node {int t, x, y;
} msj[2333];
bool cmp(node aa, node bb) {return aa.t < bb.t;
}
int T, n, m, k, c[55];
ll ans[255];
int main() {scanf("%d%d%d%d", &n, &m, &T, &k), mn = n * 5;for(int i = 1; i <= n; i++) scanf("%d", &c[i]);a = clear();for(int i = 1; i <= 4 * n; i++) a.a[i + n][i] = 0;for(int i = 1; i <= m; i++) {int u, v, w;scanf("%d%d%d", &u, &v, &w);a.a[u + n * (5 - w)][v + n * 4] = c[v];}build();for(int i = 1; i <= k; i++) scanf("%d%d%d", &msj[i].t, &msj[i].x, &msj[i].y);sort(msj + 1, msj + k + 1, cmp);for(int i = 1; i <= mn; i++) ans[i] = -inf;ans[n * 4 + 1] = c[1];for(int i = 1; i <= k; i++) {get(ans, msj[i].t - msj[i - 1].t - 1);M master = a;for(int j = 1; j <= mn; j++) master.a[j][4 * n + msj[i].x] += msj[i].y;cf(ans, master);}get(ans, T - msj[k].t);if(ans[n * 4 + 1] < 0ll) puts("-1");else printf("%lld\n", ans[n * 4 + 1]);return 0;
}

Bridges AtCoder - arc143_d

解题思路

代码实现

点击查看代码

龙门考古 UniversalOJ - 840

解题思路

代码实现

点击查看代码