luoguP2991 [USACO10OPEN]Water Slides G

题目描述过于“清晰”

最开始理解错了，以为是一个搜索，大概是预处理出每个点到终点的最长路，然后bfs，每个状态由位置、失误次数、权值和组成，不会TLE

但其实题目要求中失误是走“最坏的”，而不失误是走“最好的”；我理解的失误是走“除最好的以外的节点”（~~太nm离谱了~~）

再看原题，发现只有两种选择（最好的和最坏的），在暴搜的基础上加一个记忆化，令 $f[i][j]$ 表示从 $i$ 走到 $n$ 失误 $j$ 条边的情况下最大权值和，明显有 $f[n][0] = 0$ ， $Ans = f[1][k]$ ，由于是在一个DAG上，在搜索时转移，方程为
$$
f[u][j] =
\begin{cases}
\min(f[v][j - 1] + w_{u,v})\\
\max(f[v][j] + w_{u,v})
\end{cases}
$$
最后，记得开long long

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 5e4 + 5, M = 1.5e5 + 5, K = 10 + 5;
int n, m, k;
LL f[N][K];
bool vis[N][K];
struct Edge
{
	int ne, ver;
	LL w;
} e[M];
int h[N], idx;
void add(int x, int y, LL z)
{
	e[idx] = (Edge){h[x], y, z}, h[x] = idx++;
}
void dp(int x, int j)
{
	if (vis[x][j])
		return ;
	for (int i = h[x], y; i != -1; i = e[i].ne)
	{
		y = e[i].ver;
		dp(y, j);
		f[x][j] = max(f[y][j] + e[i].w, f[x][j]);
	}
	if (j)
		for (int i = h[x], y; i != -1; i = e[i].ne)
		{
			y = e[i].ver;
			dp(y, j - 1);
			f[x][j] = min(f[y][j - 1] + e[i].w, f[x][j]);
		}
	vis[x][j] = true;
}
int main()
{
	scanf("%d%d%d", &n, &m, &k);
	for (int i = 1; i <= n; ++i)
		h[i] = -1;
	idx = 0;
	int u, v;
	LL w;
	for (int i = 1; i <= m; ++i)
	{
		scanf("%d%d%lld", &u, &v, &w);
		add(u, v, w);
	}
	f[n][0] = 0;
	vis[n][0] = true;
	dp(1, k);
	printf("%lld\n", f[1][k]);
	return 0;
}