动态规划与图论经典问题解析：烟花观赏、巡回演出、枪战与翻转游戏
A. 观赏烟花的最大幸福值
某小镇主街被等分为 n 段，编号 1 到 n，相邻段间距为 1。节日期间有 m 场烟花表演，第 i 场烟花在时刻 ti 于位置 ai 燃放。若你在该时刻位于位置 x（1 ≤ x ≤ n），获得的幸福值为 bi - |ai - x|。你初始（时间 1）可以站在任意位置，每单位时间最多移动 d 个单位，且不能离开街道。目标是最大化所有烟花带来的幸福值总和。烟花可能同时燃放。
输入格式：第一行含三个整数 n, m, d。后续 m 行，每行三个整数 ai, bi, ti，满足 ti 非递减。
输出格式：一个整数，表示最大幸福值总和。
样例输入：
50 3 1 49 1 1 26 1 4 6 1 10
样例输出：
-31
参考解法：利用单调队列优化动态规划。设 dp[j] 表示最后一场烟花时站在位置 j 的最大幸福值，根据上一场烟花状态转移，转移范围受时间差与移动速度限制。通过维护一个递减的单调队列可以在 O(n) 内完成每轮转移。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 150002;
int n, m, d;
struct Firework { int a, b, t; } fw[N];
ll cur[N], pre[N], ans = -1e18;
int q[N];
int main() {
scanf("%d%d%d", &n, &m, &d);
for (int i = 1; i <= m; ++i) scanf("%d%d%d", &fw[i].a, &fw[i].b, &fw[i].t);
for (int i = 1; i <= m; ++i) {
memcpy(pre, cur, sizeof(cur));
if (fw[i].t == fw[i-1].t) {
for (int j = 1; j <= n; ++j)
cur[j] = pre[j] + fw[i].b - abs(fw[i].a - j);
continue;
}
ll dist = 1LL * (fw[i].t - fw[i-1].t) * d;
int head = 1, tail = 0, x = 1;
for (int j = 1; j <= n; ++j) {
while (x <= n && x <= j + dist) {
while (head <= tail && pre[x] >= pre[q[tail]]) --tail;
q[++tail] = x; ++x;
}
while (head <= tail && q[head] < j - dist) ++head;
cur[j] = pre[q[head]] + fw[i].b - abs(fw[i].a - j);
}
}
for (int i = 1; i <= n; ++i) ans = max(ans, cur[i]);
printf("%lld", ans);
return 0;
}
B. 乐团巡回演出
乐团计划从城市 1 出发，每天搭乘航班飞往另一城市，经过 k 天后抵达城市 n。共有 n 座城市（2 ≤ n ≤ 10），每对城市间有一份循环航班表。对于从城市 i 到 j 的航班，给定一个周期长度 d（1 ≤ d ≤ 30）和 d 个非负整数，依次代表第 1 天至第 d 天的票价，0 表示当天无航班，之后循环。求 k 天旅行的最小总费用，若无法完成则输出 0。输入包含多个场景，以 n = k = 0 结束。
输入格式：每个场景以 n 和 k 开始，接下来 n*(n-1) 行航班表。先给出从城市 1 到其他城市的表（除 1 外），然后城市 2 到其他城市，依此类推。每份表第一个数为周期 d，随后 d 个整数。
输出格式：每个场景一行，输出最小费用或 0。
样例输入：
3 6 2 130 150 3 75 0 80 7 120 110 0 100 110 120 0 4 60 70 60 50 3 0 135 140 2 70 80 2 3 2 0 70 1 80 0 0
样例输出：
460 0
参考解法：使用二维 dp，dp[day][city] 表示第 day 天位于 city 的最小花费。转移时需要根据天数对周期取模得到当天票价，若值为 0 则略过。注意天数从 1 开始，最终检验第 k+1 天抵达城市 n 的费用。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 0x3f3f3f3f3f3f3f3f;
int n, K;
struct Flight {
int period;
int cost[32];
} f[11][11];
ll dp[1002][11];
int getDay(int day, int p) {
return (day - 1) % p + 1;
}
int main() {
while (scanf("%d%d", &n, &K), n || K) {
memset(f, 0, sizeof(f));
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j) {
if (i == j) continue;
int d; scanf("%d", &d);
f[i][j].period = d;
for (int t = 1; t <= d; ++t)
scanf("%d", &f[i][j].cost[t]);
}
memset(dp, 0x3f, sizeof(dp));
dp[1][1] = 0;
for (int day = 2; day <= K + 1; ++day) {
for (int v = 1; v <= n; ++v) {
for (int u = 1; u <= n; ++u) {
if (u == v) continue;
int idx = getDay(day - 1, f[u][v].period);
int price = f[u][v].cost[idx];
if (price == 0) continue;
dp[day][v] = min(dp[day][v], dp[day-1][u] + price);
}
}
}
if (dp[K+1][n] > 1e15) puts("0");
else printf("%lld\n", dp[K+1][n]);
}
return 0;
}
C. 枪战：最小与最大死亡人数
n 个人从 1 到 n 编号，每人有一把手枪且瞄准一个对象（可能瞄准自己）。他们按某种顺序依次开枪，每次仅一人射击。你的任务是计算在所有可能的开枪顺序中，最终死亡人数的最小可能值和最大可能值。
输入格式：第一行为 n (n < 1e6)，第二行为 n 个整数，依次表示第 i 个人的瞄准目标。
输出格式：两个整数，分别代表最小死亡人数和最大死亡人数。
样例输入：
8 2 3 2 2 6 7 8 5
样例输出：
3 5
参考解法：该模型可转化为基环树（每个节点出度为 1）。先拓扑排序处理入度为 0 的节点：它们一定可以存活，且它们的射击目标必然死亡，由此可以连锁推导。剩余节点位于环上。对于每个环，若其长度大于 1 且不包含已被断定死亡的人，最小存活数可加 1（一个环可保留一个存活者，除非环大小为 1 且为自杀则无额外存活）。最大死亡数方面，入度为 0 的点推导出的死亡以及每个环除一人外全死可以求得。利用队列进行拓扑删点并统计。
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
int target[N], indeg[N];
bool dead[N], willDie[N];
int main() {
int n; scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
scanf("%d", target + i);
indeg[target[i]]++;
}
queue<int> q;
int alive = 0, deadMax = 0;
for (int i = 1; i <= n; ++i)
if (indeg[i] == 0) q.push(i);
while (!q.empty()) {
int u = q.front(); q.pop();
alive++; // 入度为0者可存活
int v = target[u];
if (!dead[v]) {
dead[v] = true; deadMax++;
int w = target[v];
if (--indeg[w] == 0) q.push(w);
willDie[w] = true; // w 在后续处理中也必然死亡（用于最大死亡）
}
}
for (int i = 1; i <= n; ++i) {
if (indeg[i] && !dead[i]) {
int len = 0;
bool hasDie = false;
for (int j = i; !dead[j]; j = target[j]) {
dead[j] = true;
len++;
if (willDie[j]) hasDie = true;
}
if (len > 1 && !hasDie) alive++; // 独立的非自环可以留一个活口
deadMax += len - 1; // 环中最多死 len-1 人
if (hasDie) deadMax++; // 若有外部传入的死亡标记，环上实际可全灭
}
}
printf("%d %d\n", n - deadMax, n - alive);
return 0;
}
D. 翻转游戏
有一个 4×4 的棋盘，每个格子放有一枚双面棋子（一面黑一面白）。每步操作可以选择一个格子翻转，同时其上、下、左、右的相邻棋子（如果存在）也会一起翻转。给定初始状态（'b' 黑，'w' 白），求将全部棋子翻成同一种颜色的最少步数，若无法达成则输出 "Impossible"。
输入格式：4 行，每行 4 个字符，代表初始状态。
输出格式：最少步数或 "Impossible"。
样例输入：
bwwb bbwb bwwb bwww
样例输出：
4
参考解法：采用逐行确定的方法。枚举第一行的按压模式（共 2^4 种），然后从第二行开始，每一行的按压方案必须使得上一行全部变成目标颜色。这样逐行递推到底后，只需检查最后一行是否符合要求。分别尝试目标为全白或全黑，取最小步数。
#include <bits/stdc++.h>
using namespace std;
int board[6][6], tmp[6][6];
const int n = 4;
const int INF = 1e9;
void press(int x, int y) {
tmp[x][y] ^= 1;
if (x > 1) tmp[x-1][y] ^= 1;
if (x < n) tmp[x+1][y] ^= 1;
if (y > 1) tmp[x][y-1] ^= 1;
if (y < n) tmp[x][y+1] ^= 1;
}
int solve(int target) {
int ans = INF;
for (int mask = 0; mask < (1 << n); ++mask) {
memcpy(tmp, board, sizeof(tmp));
int steps = 0;
for (int j = 0; j < n; ++j)
if (mask & (1 << j)) { press(1, j+1); steps++; }
for (int i = 2; i <= n; ++i)
for (int j = 1; j <= n; ++j)
if (tmp[i-1][j] != target) {
press(i, j); steps++;
}
bool ok = true;
for (int j = 1; j <= n; ++j)
if (tmp[n][j] != target) ok = false;
if (ok) ans = min(ans, steps);
}
return ans;
}
int main() {
for (int i = 1; i <= n; ++i) {
char s[5]; scanf("%s", s);
for (int j = 0; j < 4; ++j)
board[i][j+1] = s[j] == 'b' ? 1 : 0;
}
int ans = min(solve(0), solve(1));
if (ans == INF) puts("Impossible");
else printf("%d\n", ans);
return 0;
}
