P11676 [USACO25JAN] DFS Order P

题意：

有一个

n

个点的无向图和一个

n \times n

的矩阵

a

，

a_{i,j} > 0

说明这条边当前不在，加入的代价是

a_{i,j}

，

a_{i,j} < 0

说明这条边当前在，删除的代价是

-a_{i,j}

。

可以增删一些边，使得存在一个 dfs 序是

1,2,3,\dots,n

。

n \le 750

。

思路：

这个数据范围不是网络流就是 dp，经过尝试会发现网络流不太好做，考虑 dp。

如果我们当前搜到了

i

，则我们要求除了走过来的这条边，

i

不能和前面的点有任何连边。

我们考虑区间 dp：设

f(i,j)

表示进入

i

的子树中，最后一个搜完的是

j

。

首先，有

\sum_{k=j+1}^n \max\{0,-a_{i,k}\}

的代价，因为如果

j

之后

i

回溯了那么是不能和后面有边的。

我们先不考虑这个代价，我们类似树形

dp

考虑一个子树一个子树的加入。

枚举一个

j

，考虑能转移到哪些状态。

我们枚举下一个子树到

k

，则转移就是：

f(i,j) + f(j+1,j+k) + \max\{0,a_{i,j+1}\} \to f(i,j+k)

这样就能

O(n^2)

求出所有

f_i(j)

，总的时间复杂度就是

O(n^3)

。

CPP

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 755;
const int inf = 0x3f3f3f3f;

int n;
int a[N][N] = {{0}};

int f[N][N] = {{0}}, g[N][N] = {{0}};
void cmn(int &x, int y) {
	x = min(x, y);
}

int main() {
	scanf("%d", &n);
	for (int i = 2; i <= n; i++)
		for (int j = 1; j < i; j++)
			scanf("%d", &a[j][i]);
	for (int i = 1; i <= n; i++) {
		for (int j = i + 1; j <= n; j++)
			g[i][j] = max(0, -a[i][j]);
		for (int j = n - 1; j >= i + 1; j--)
			g[i][j] += g[i][j + 1];
	}
	memset(f, 0x3f, sizeof f);
	for (int i = n; i >= 1; i--) {
		f[i][i] = 0;
		for (int j = i; j <= n; j++) {
			if (f[i][j] != inf) {
				for (int k = 1; j + k <= n; k++) {
					cmn(f[i][j + k], f[i][j] + f[j + 1][j + k] + max(0, a[i][j + 1]));
				}
			}
		}
		for (int j = i; j <= n; j++)
			f[i][j] += g[i][j + 1];
	}
	cout << f[1][n] << endl;
	return 0;
}

P11676 [USACO25JAN] DFS Order P

文章操作

P11676 [USACO25JAN] DFS Order P

相关推荐

评论

P11676 [USACO25JAN] DFS Order P