【luogu AT5147】Negative Cycle（差分约束）（DP）

Negative Cycle

题目链接：luogu AT5147

题目大意

给你一个有向图，有 i 到 i+1 的边，边权为 0。
然后对于不相等的 i,j 之间，有一条 i 到 j 的边，如果从小到大边权为 -1，否则为 1，然后可以被你删去，有一个费用 ai,j。
然后要你用最小的费用使得图中不存在负环。

思路

首先由一个转化就是看到负环那存在的条件就是差分约束无解。
（因为你发现正常来搞好像不太能看负环之类的）

然后看到有不能被删的边，考虑从它下手，发现条件是 $x_i⩾x_{i+1}$

然后接着看可以删掉的：
$i\to j(i<j):x_i-1⩾x_j$
$i\to j(i>j):x_i+1⩾x_j$

然后因为好观察所以我们让 $i<j$，那应该是：
$i\to j(i<j):x_i-1⩾x_j$
$j\to i(i<j):x_j+1⩾x_i$
整理一下：
$x_i-x_j⩾1$
$x_i-x_j⩽1$

考虑怎么跟上面的那个联系起来，发现上面那个可以变成：
$x_i-x_{i+1}⩾0$
然后就是类似于差分的形式，然后那连续的差分加起来就是头减尾。
那不就跟上面的那个一样了吗！
设 $y_i=x_i-x_{i+1}⩾0$，那两个条件就是 $\sum _{p=i}^j{y}_i⩾1$ 和 $⩽1$

那也就是条件是不能 $<1,>1$ 这两种，那显然的我们的取值由于 $y⩾0$ 就只能是 $0/1$（整数）。
那我们可以看到我们所要注意的就是相邻的 $1$ 之间的位置，具体而言我们放一个 $1$ 的时候要注意前面两个 $1$ 的位置。
因为两个 $1$ 之间是 $<1$ 要用贡献删去。
到前面的那个 $1$ 的位置的时候积累了两个 $1$，就也要用贡献。

$f_{i,j}$ 为倒数那个在 $i$，倒数两个在 $j$，DP 转移即可。
至于转移系数那些，考虑每次到一个位置，那之前的 $f_{i,j}$ 加贡献因为无论放不放这个位置到前面那些的都会有，然后在看是不是放把下标转移一下。
那你加的是一段的贡献，这个简单直接前缀和预处理一下就可以了。

代码

#include
#include
#include
#define ll long long

using namespace std;

const int N = 505;
int n, a[N][N];
ll f[N][N], ans, sb[N][N], bs[N][N];
//sb:small big
//bs:big small

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++) {
			if (i == j) continue;
			scanf("%d", &a[i][j]);
		}
	
	for (int i = 1; i <= n; i++)
		for (int j = i; j <= n; j++)
			sb[i][j] = sb[i - 1][j] + a[i][j];
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= i; j++)
			bs[i][j] = bs[i][j - 1] + a[i][j];
	
	memset(f, 0x7f, sizeof(f));
	f[1][1] = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j < i; j++)
			for (int k = 1; k <= j - !!(j - 1); k++)
				f[i][j] = min(f[i][j], f[j][k]);
		for (int j = 1; j <= i; j++)
			for (int k = 1; k <= j - !!(j - 1); k++)
				f[j][k] += (sb[i][i] - sb[j - 1][i]) + (bs[i][k - 1]);
	}
	ans = f[0][0];
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			ans = min(ans, f[i][j]);
	printf("%lld", ans);
		
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46