On the subject

Topic link :https://www.luogu.com.cn/problem/AT5147

The main idea of the topic

Yes $n$ A picture of points , among $i\to i+1(i<n)$ There is an edge with a weight of $0$.

For others $i,j(i\ne j)$ There is an edge $i\to j$, if $i<j$ So the weight is $-1$, Otherwise $1$.

Delete $i\to j(i\ne j)$ The price is $a_{i,j}$, The minimum cost is required so that there is no negative ring in the graph .

$1\le n\le 500$

Their thinking

This easy negative ring makes people confused and don't know how to maintain , We know that the condition for the solution of the difference constraint is that there is no negative ring , So we can consider transforming it into a differential constraint model .

Then for edges that cannot be deleted $i\to i+1$ There are limits $x_i\ge x_{i+1}$, That is, the whole sequence is monotonous .

Then it looks like $i\to j(i<j)$ Can be regarded as $x_i-1\ge x_j$.
Form like $i\leftarrow j(i<j)$ Can be regarded as $x_i\le x_j+1$.

That is to say $x_i-x_j\le 1$ and $x_i-x_j\ge 1$ The limitation of , We consider maintaining differential arrays （ On the contrary ）$y_i=x_{i-1}-x_i$, Then the condition is that the sum of intervals cannot be greater than / Less than $1$, Obviously, so $y_i$ It can only be $0/1$.

Then carefully observe this limit and you will find that there are only adjacent $1$ It will work , We consider the $dp$ To deal with it , set up $f_{i,j,k}$ Means to achieve the second goal $i$ individual , the previous $1$ stay $j$ It's about , One more $1$ stay $k$ It's about .

Prefix and $a$ Array optimization can be transferred .

Time complexity ：$O(n^3)$

code

#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const ll N=510;
ll n,a[N][N],s[N][N],t[N][N],f[N][N],ans;
signed main()
{
    
	scanf("%lld",&n);
	for(ll i=1;i<=n;i++)
		for(ll j=1;j<=n;j++){
    
			if(i==j)continue;
			scanf("%lld",&a[i][j]);
		}
	for(ll i=1;i<=n;i++)
		for(ll j=1;j<=i;j++)
			s[i][j]=s[i][j-1]+a[j][i],
			t[i][j]=t[i][j-1]+a[i][j];
	memset(f,0x3f,sizeof(f));
	ans=f[0][0];f[1][1]=0;
	for(ll i=2;i<=n;i++){
    
		for(ll j=1;j<i;j++)
			for(ll k=1;k<=j-(j!=1);k++)
				f[i][j]=min(f[i][j],f[j][k]);
		for(ll j=1;j<=i;j++)
			for(ll k=1;k<=j-(j!=1);k++)
				f[j][k]+=s[i][i]-s[i][j-1],f[j][k]+=t[i][k-1];
	}
	for(ll i=1;i<=n;i++)
		for(ll j=1;j<=n;j++)
			ans=min(ans,f[i][j]);
	printf("%lld\n",ans);
	return 0;
}