本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-01-05 09:14:57

题目大意：

给定一个类似从中心的切三角形西瓜的图，你删去一些边，使图成为二分图，且删去边权和最小。

做法：

图论转环形dp

最小删边数,保留的最大。不断增加

假设0点染0色

f[i][0/1]代表处理1..i个点，i个点与染什么颜色。 从离散的点开始加边。

确定起点。

#include<bits\/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+9; 
ll a[N],b[N],n,f[N][2],ans,s=0; 
void work(int flag,ll x){
	memset(f,-32,sizeof(f)); \/\/初始化，求最大值用最小值初始化。（写错丢分） 
	f[1][flag]=x;\/\/不能与0点相连的  
	for(int i=2; i<=n; ++i)
    {
        f[i][0] = max(f[i-1][0], f[i-1][1] + b[i-1]);\/\/可以与染1色的相连 
        f[i][1] = max(f[i-1][0] + b[i-1] , f[i-1][1]) + a[i];\/\/可以与染0的i-1点相连。还可以与0点相连 
    }
    return ;
} 
int main(){

	cin>>n;
	for(int i=1;i<=n;i++) scanf("%lld",&a[i]),s+=a[i];
	for(int i=1;i<=n;i++) scanf("%lld",&b[i]),s+=b[i];
	work(0,0);
	ans=max(f[n][0],f[n][1]+b[n]);
	work(1,a[1]);
	ans=max(ans,max(f[n][1],f[n][0]+b[n]));
	
	cout<<s-ans<<endl;	
}