Trie树原理与实现
注：本文部Ñ …
月度归档： 2018 年 2 月
![[AHOI2009]中国象棋 题解](https://ksmeow.moe/wp-content/uploads/2018/02/180205c-400x400.png "180205c")
![[NOIP2009普及]道路游戏 题解](https://ksmeow.moe/wp-content/uploads/2018/02/180205b.png "180205b")
[NOIP2009普及]道路游戏 题解
题目地址：洛谷：【P1070】道路游戏 – 洛谷
题目描述
小新正在玩一个简单的电脑游戏。
游戏中有一条环形马路，马路上有 n 个机器人工厂，两个相邻机器人工厂之间由一小段马路连接。小新以某个机器人工厂为起点，按顺时针顺序依次将这 n 个机器人工厂编号为1~n，因为马路是环形的，所以第 n 个机器人工厂和第 1 个机器人工厂是由一段马路连接在一起的。小新将连接机器人工厂的这 n 段马路也编号为 1~n，并规定第 i 段马路连接第 i 个机器人工厂和第 i+1 个机器人工厂（1≤i≤n-1），第 n 段马路连接第 n 个机器人工厂和第 1个机器人工厂。
游戏过程中，每个单位时间内，每段马路上都会出现一些金币，金币的数量会随着时间发生变化，即不同单位时间内同一段马路上出现的金币数量可能是不同的。小新需要机器人的帮助才能收集到马路上的金币。所需的机器人必须在机器人工厂用一些金币来购买，机器人一旦被购买，便会沿着环形马路按顺时针方向一直行走，在每个单位时间内行走一次，即从当前所在的机器人工厂到达相邻的下一个机器人工厂，并将经过的马路上的所有金币收集给小新，例如，小新在 i（1≤i≤n）号机器人工厂购买了一个机器人，这个机器人会从 i 号机器人工厂开始，顺时针在马路上行走，第一次行走会经过 i 号马路，到达 i+1 号机器人工厂（如果 i=n，机器人会到达第 1 个机器人工厂），并将 i 号马路上的所有金币收集给小新。 游戏中，环形马路上不能同时存在 2 个或者 2 个以上的机器人，并且每个机器人最多能够在环形马路上行走 p 次。小新购买机器人的同时，需要给这个机器人设定行走次数，行走次数可以为 1~p 之间的任意整数。当马路上的机器人行走完规定的次数之后会自动消失，小新必须立刻在任意一个机器人工厂中购买一个新的机器人，并给新的机器人设定新的行走次数。
以下是游戏的一些补充说明：
- 游戏从小新第一次购买机器人开始计时。
- 购买机器人和设定机器人的行走次数是瞬间完成的，不需要花费时间。
- 购买机器人和机器人行走是两个独立的过程，机器人行走时不能购买机器人，购买完机器人并且设定机器人行走次数之后机器人才能行走。
- 在同一个机器人工厂购买机器人的花费是相同的，但是在不同机器人工厂购买机器人的花费不一定相同。
- 购买机器人花费的金币，在游戏结束时再从小新收集的金币中扣除，所以在游戏过程中小新不用担心因金币不足，无法购买机器人而导致游戏无法进行。也因为如此，游戏结束后，收集的金币数量可能为负。
现在已知每段马路上每个单位时间内出现的金币数量和在每个机器人工厂购买机器人需要的花费，请你告诉小新，经过 m 个单位时间后，扣除购买机器人的花费，小新最多能收集到多少金币。
输入输出格式
输入格式：
第一行 3 个正整数，n，m，p，意义如题目所述。
接下来的 n 行，每行有 m 个正整数，每两个整数之间用一个空格隔开，其中第 i 行描述了 i 号马路上每个单位时间内出现的金币数量（1≤金币数量≤100），即第 i 行的第 j（1≤j≤m）个数表示第 j 个单位时间内 i 号马路上出现的金币数量。
最后一行，有 n 个整数，每两个整数之间用一个空格隔开，其中第 i 个数表示在 i 号机器人工厂购买机器人需要花费的金币数量（1≤金币数量≤100）。
输出格式：
共一行，包含 1 个整数，表示在 m 个单位时间内，扣除购买机器人花费的金币之后，小新最多能收集到多少金币。
输入输出样例
输入样例#1：
2 3 2 1 2 3 2 3 4 1 2
输出样例#1：
5
说明
【数据范围】
对于 40%的数据，2≤n≤40，1≤m≤40。
对于 90%的数据，2≤n≤200，1≤m≤200。
对于 100%的数据，2≤n≤1000，1≤m≤1000，1≤p≤m。
NOIP 2009 普及组 第四题
题解
这里我采用的是GhastIcon同学的思路。可以在这里P1070 道路游戏 题解找到他的题解。
最初的想法
设计状态dp[i]为到第i时刻获得的最大金币数，转移可以通过枚举这个时刻到的位置和走过的步数来实现，方程如下
dp[i] = \max \{dp[i - t] + g[i][s - 1] - g[i][s - t - 1] - c[s - t]\}
具体解释一下上面的各个变量。t是枚举的步数，s是枚举的当前位置。i-t表示t时间前的时刻，p-t表示t时间前的位置（要注意处理一下让它在1~n范围内），g表示一种斜线的前缀和，c表示在这个位置买机器人的开销。可以知道我们的收益在题目给的那个表上是对角线上计算的，以样例为例，两种斜线前缀和如下图。
![180205b 1 - [NOIP2009普及]道路游戏 题解](https://ksmeow.moe/wp-content/uploads/2018/02/180205b-1.jpg "[NOIP2009普及]道路游戏 题解")
由此我们知道这个DP是O(mn^2)的。这种思路对于这道题来说不够优。我们需要优化。
降低时间：单调队列
整理一下DP方程。
dp[i] = \max \{dp[i - t] - g[i][s - t - 1] - c[s - t]\} + g[i][s - 1]
我们发现max标记里面的这个值其实可以单调队列处理，因为枚举的t有一个范围1 \leq t \leq p。设一个 h[i][j] = dp[i] - g[i][j - 1] - c[j] ，用h代换方程中的max里面的部分，单调队列维护的就是这个h。对于h的每一个j创建单调队列，在更新i的同时更新单调队列，这样就可以达到降低时间复杂度的目的。转移变为O(n)。
这里的思路去发现依赖关系和最值转移关系。
其他优化？
感觉dp数组都可以拿掉了，因为最后dp出来的值都是要插入单调队列里面的。可以稍稍优化空间常数。
实现细节
初始值要设成买一个机器人的开销。以及我代码中的deque可以全换成手写双端队列，STL比较慢。
代码
// Code by KSkun, 2018/2
#include <cstdio>
#include <cstring>
#include <deque>
#include <utility>
typedef std::pair<int, int> PI;
std::deque<PI> que[1005];
int n, m, p, sum[1005][1005], cost[1005], dp[1005], v;
inline int minus(int a, int b) { // return a - b
return ((a - b) % n + n) % n;
}
int main() {
scanf("%d%d%d", &n, &m, &p);
for(int i = 0; i < n; i++) {
for(int j = 1; j <= m; j++) {
scanf("%d", &sum[i][j]);
}
}
for(int i = 0; i < n; i++) {
scanf("%d", &cost[i]);
}
// 处理对角线前缀和
for(int i = 2; i <= m; i++) {
for(int j = 0; j < n; j++) {
sum[j][i] += sum[minus(j, 1)][i - 1];
}
}
// 设置初值表示开始一定要买一个机器人
for(int i = 0; i < n; i++) {
que[minus(i, -1)].push_back(std::make_pair(-cost[i], 0));
}
memset(dp, 0xc0, sizeof dp);
for(int i = 1; i <= m; i++) {
for(int j = 0; j < n; j++) {
dp[i] = std::max(dp[i], que[minus(j, i - 1)].front().first + sum[minus(j, 1)][i]);
}
for(int j = 0; j < n; j++) {
while(!que[minus(j, i - 1)].empty() && i - que[minus(j, i - 1)].front().second >= p) {
que[minus(j, i - 1)].pop_front();
}
v = dp[i] - sum[minus(j, 1)][i] - cost[j];
while(!que[minus(j, i - 1)].empty() && que[minus(j, i - 1)].back().first <= v) {
que[minus(j, i - 1)].pop_back();
}
que[minus(j, i - 1)].push_back(std::make_pair(v, i));
}
}
printf("%d", dp[m]);
return 0;
}
![[ZJOI2004]午餐 题解](https://ksmeow.moe/wp-content/uploads/2018/02/180205a.png "180205a")
![[ZJOI2007]棋盘制作 题解](https://ksmeow.moe/wp-content/uploads/2018/02/180204.png "180204")
DP的花式优化方法
本文章可能不会继续更新，可以在单独的题解里面找找有没有有趣的DP题目。
这里不分类介绍具体的优化方法，而是收集一些比较有意思的题目，从题目出发讲优化。
一些优化手段：
[NOI2005]瑰丽华尔兹：从4次方到3次方
朴素的想法
这个题是一个DP问题，设计状态为dp[i, j, k]为在(i, j)处，k时间段末的滑行最长距离。考虑从上一时间段转移过来，如果不考虑障碍物，假设在第一坐标上移动，转移方程应该如下：
dp[i, j, k] = \max \{dp[i', j, k - 1] + i - i'\} \ (i - i' \leq t)
对于每一个时间段k，对于每一个点(i, j)进行时间段方向上的转移，单次转移遍历该方向的点，复杂度为1次。遍历地图的复杂度为2次，遍历时间段的复杂度为1次，总和即为4次。
对于200的数据，4次显然是不够的，考虑优化这一过程。
降低时间：单调队列
我们发现这个题可以维护区间上长度为t的一段 dp[i', j, k - 1] - i' 的最大值，这个过程可以用单调队列降掉1次。3次的复杂度是可以接受的。
降低空间：滚动数组
注意到转移只跟上一层即k-1有关系，这就可以对这一维进行滚动。空间减少1次。滚动数组对cache友好，还能优化下常数。
降低空间：降维
转移具有一定的方向性，如果按照一定顺序转移可以达到更新而不发生错误的效果。经过分析后，k这一维可以删去。
说了这么多，没代码说个**
那就给你们代码嘛。
// Code by KSkun, 2018/2
#include <cstdio>
#include <cstring>
#include <algorithm>
const int NINF = 0xc0c0c0c0;
const int fix[5][5] = {{0, -1, 1, 0, 0}, {0, 0, 0, -1, 1}};
int n, m, x, y, k, dp[205][205], si, ti, di, que[205], pos[205], l, r, v, now, ans = -1;
char mmp[205][205];
inline void workdp(int nx, int ny, int d, int t) {
l = r = 1;
now = 1;
while(nx <= n && ny <= m && nx >= 1 && ny >= 1) {
if(mmp[nx][ny] == 'x') {
l = r = 1;
}
v = dp[nx][ny] - now;
if(v >= NINF) {
while(l < r && que[r - 1] <= v) r--;
que[r] = v;
pos[r] = now;
r++;
}
while(l < r && now - pos[l] > t) l++;
if(l < r) {
dp[nx][ny] = que[l] + now;
} else {
dp[nx][ny] = NINF;
}
ans = std::max(ans, dp[nx][ny]);
nx += fix[0][d];
ny += fix[1][d];
now++;
}
}
int main() {
scanf("%d%d%d%d%d", &n, &m, &x, &y, &k);
for(int i = 1; i <= n; i++) {
scanf("%s", mmp[i] + 1);
}
memset(dp, 0xc0, sizeof dp);
dp[x][y] = 0;
while(k--) {
scanf("%d%d%d", &si, &ti, &di);
if(di == 1) {
for(int i = 1; i <= m; i++) workdp(n, i, di, ti - si + 1);
}
if(di == 2) {
for(int i = 1; i <= m; i++) workdp(1, i, di, ti - si + 1);
}
if(di == 3) {
for(int i = 1; i <= n; i++) workdp(i, m, di, ti - si + 1);
}
if(di == 4) {
for(int i = 1; i <= n; i++) workdp(i, 1, di, ti - si + 1);
}
}
printf("%d", ans);
return 0;
}
宝物筛选_NOI导刊2010提高（02）：多重背包的二进制优化和单调队列优化
多重背包的二进制优化
说明
如果将一个数字拆成1, 2, 4, 8, \cdots , 2^n, n - 2^n这些数字，可以证明这些数字可以组合成1~n的任意一个数字，对每个物品的数量如此拆分，即可转换为01背包问题。这样的复杂度是O(V * \sum (\log n_i))的。
代码
// Code by KSkun, 2018/2
#include <cstdio>
#include <algorithm>
struct io {
char buf[1 << 26], *s;
io() {
fread(s = buf, 1, 1 << 26, stdin);
}
inline int read() {
register int res = 0, neg = 1;
while(*s < '0' || *s > '9') if(*(s++) == '-') neg = -1;
while(*s >= '0' && *s <= '9') res = res * 10 + *s++ - '0';
return res * neg;
}
} ip;
#define read ip.read
int n, w, val, wei, num, dp[40005], j;
int main() {
n = read();
w = read();
for(int i = 1; i <= n; i++) {
val = read();
wei = read();
num = read();
for(j = 0; (1 << (j + 1)) - 1 <= num; j++) {
for(int k = w; k >= wei * (1 << j); k--) {
dp[k] = std::max(dp[k], dp[k - wei * (1 << j)] + val * (1 << j));
}
}
if((1 << j) - 1 < num) {
j = num - ((1 << j) - 1);
for(int k = w; k >= wei * j; k--) {
dp[k] = std::max(dp[k], dp[k - wei * j] + val * j);
}
}
}
printf("%d", dp[w]);
return 0;
}
多重背包的单调队列优化
说明
回到最原始的转移方程：
dp[i][j] = \max \{dp[i - 1][j - k * c_i] + k * v_i\} \ (0 \leq k \leq \min (n_i, \lfloor \frac{j}{c_i} \rfloor))
这里的转移，一定是从比j小c_i整数倍的位置转移而来。我们可以讨论j模c_i的值，对一个剩余类内部进行单调队列的转移。从 (j \mod c_i) + k * c_i 这个状态往 (j \mod c_i) + k' * c_i \ (k' \geq k) 这个状态转移。这样做复杂度可以减为 O(V * N) 。
当然你还可以对i维度进行滚动数组优化空间。
代码
// Code by KSkun, 2018/2
#include <cstdio>
#include <algorithm>
struct io {
char buf[1 << 26], *s;
io() {
fread(s = buf, 1, 1 << 26, stdin);
}
inline int read() {
register int res = 0, neg = 1;
while(*s < '0' || *s > '9') if(*(s++) == '-') neg = -1;
while(*s >= '0' && *s <= '9') res = res * 10 + *s++ - '0';
return res * neg;
}
} ip;
#define read ip.read
inline int g(int i) {
return i & 1;
}
int n, w, val, wei, num, que[40005], pos[40005], l, r, dlt, v, dp[2][40005];
int main() {
n = read();
w = read();
for(int i = 1; i <= n; i++) {
val = read();
wei = read();
num = read();
for(int j = 0; j < wei; j++) {
l = r = 1;
dlt = 0;
for(int k = 0; j + k * wei <= w; k++) {
v = dp[g(i - 1)][j + k * wei] - dlt;
while(l < r && que[r - 1] <= v) r--;
que[r] = v;
pos[r] = k;
r++;
while(l < r && k - pos[l] > num) l++;
dp[g(i)][j + k * wei] = std::max(dp[g(i)][j + k * wei], que[l] + dlt);
dlt += val;
}
}
}
printf("%d", dp[g(n)][w]);
return 0;
}
