AGC036D
有个大小为(n)的有向图，其中有(n-1)条不可以删的边，连着((i,i+1))。
对于任意((x,y),x eq y)，都有这样的边：如果(x<y)，那么((x,y))连一条(-1)的边。如果(x>y)，那么((x,y))连一条(1)的边。
这些都是可以删的边，每条边都有个删除的代价。
现在要删除代价和尽量少的边，使得图中不存在负环。
蛤蛤听说正解是差分约束？。。。
讲讲我想了一天的毒瘤做法。
首先有个出现负环的充要条件：对于一条正边((u,v))，若有一条负边((x,y))，满足(vle xle yle u)，那么区间([v,x])和([y,u])缩成一个点（意味着可以以(0)的代价互相到达）。一直缩到不能再缩为止。此时出现负环，当且仅当存在一个点有负自环。
这还挺容易证明的。尽管我第一天晚上看题第二天中午才发现了这条性质。
考虑保留尽量边权和尽量大的边。我们考虑下最优解长成什么样子：
-
如果一条正边((u,v))在答案中，那么正边((u,w)(w>v))一定出现在答案中。
如果一条负边((x,y))在答案中，那么负边((z,y)(z<x))一定出现在答案中。
前缀和、后缀和一下，那么对于每个右端点只需要考虑以它为右端点的正边和负边。
-
在上面这条性质的条件下（意味着每个右端点只需要考虑一条正边和一条负边）。
一定不存在两条正边（或负边）的区间互相包含。所以随着右端点递增，左端点也跟着递增。
-
考虑如下的局部结构：
红色的那一片为缩成一个点的区域。
由于希望它最优，所以两段红色区域中，左边区域中每个点到右边区域中每个点都有边（不管是正边还是负边）。推广：对于任意两个缩成一个点的区域，它们之间若有边，那么实际上内部的点都是互相有边。
（这个局部结构可以推广：定义当(k=j-1)时，表示([j,i])之间没有负边。这时候就不存在这个红色区域。但在下面DP转移的时候，可以发现实际上可以用同一条式子。）
于是实际上长这样：
(不存在某个右端点没有连正边的，如果没有连，连一下不亏。)
- 然后还可以证明右边的那段红色区域的左端点为(k+1)：如果左端点大于(k+1)，考虑(k)和左端点之间的某个点。考虑以它为右端点时正边连向哪里，由于上面的第2条性质，一定会连到(j)或之前的某个点。如果连到(j)，不如和右边那段区域缩在一起；如果连到(j)之前，那么一定不会在(k)连向的左端点的左边。结合第3条性质的那个图，连向的位置和(k)连向的在同一个区域（归纳，前面的位置已经满足了第4条性质，如果前面没有了那就只能连向(j)了），那不如和左边那段区域缩在一起。
然后我们可以用(f_{i,j,k})来表示状态：做到第(i)个点，(j)和(k)分别如上面所示。
转移：
(f_{i,j,k} o f_{i+1,j,k}+posi(i+1,j)+nega(i+1,k))，表示和前面的合成一块。
(f_{i,j,k} o f_{i+1,k+1,i}+posi(i+1,k+1)+nega(i+1,i))，表示新开一块。
时间复杂度(O(n^3))。
using namespace std;
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 510
#define ll long long
int n;
int a[N][N];
ll p[N][N],q[N][N];
ll f[2][N][N];
void upd(ll &a,ll b){a=max(a,b);}
int main(){
scanf("%d",&n);
ll sum=0;
for (int i=1;i<=n;++i){
for (int j=1;j<i;++j)
scanf("%d",&a[i][j]),sum+=a[i][j];
for (int j=i+1;j<=n;++j)
scanf("%d",&a[i][j]),sum+=a[i][j];
}
for (int i=1;i<=n;++i){
for (int j=i-1;j>=1;--j)
p[i][j]=p[i][j+1]+a[i][j];
for (int j=1;j<i;++j)
q[i][j]=q[i][j-1]+a[j][i];
}
int now=1,las=0;
memset(f[now],128,sizeof f[now]);
f[now][1][0]=0;
for (int i=1;i<n;++i){
swap(now,las);
memset(f[now],128,sizeof f[now]);
for (int j=1;j<=i;++j)
for (int k=j-1;k<i;++k)
if (f[las][j][k]>=0){
upd(f[now][j][k],f[las][j][k]+p[i+1][j]+q[i+1][k]);
upd(f[now][k+1][i],f[las][j][k]+p[i+1][k+1]+q[i+1][i]);
}
}
ll ans=0;
for (int j=1;j<=n;++j)
for (int k=j-1;k<n;++k)
upd(ans,f[now][j][k]);
printf("%lld
",sum-ans);
return 0;
}