【2024NOIP集训娱乐赛6】LIS 做题记录

有一个 $n$ 的排列 $a$，删除 $a_i$ 的代价为 $b_i$，对于每个 $k\in[1,n]$，求使得 $a$ 的 LIS（最长上升子序列）长度 $\le k$ 的最小代价。

$1\le n\le 500$，$1\le b_i\le 10^6$。

如果想到分层图那么就输了。

首先，最长链等于最小反链覆盖，所以 $a$ 的 LIS 长度为 $k$ 相当于至少需要 $k$ 个不降子序列覆盖 $a$。

也就是说，若能用 $k$ 个不降子序列覆盖 $a$，则 $a$ 的 LIS 长度一定 $\le k$。

考虑先删除所有数，再加入代价和最大的数使得 $a$ 的 LIS 长度 $\le k$。这相当于找到 $\le k$ 个不降子序列使得它们不交且代价和最大。

那么考虑费用流，将 $i$ 拆为入点 $x_i$ 和出点 $y_i$：

• 源点向 $x_i$ 连流量为 $\infin$，费用为 $0$ 的边；
• $x_i$ 向 $y_i$ 连流量为 $1$，费用为 $-b_i$ 的边；
• $y_i$ 向汇点连流量为 $\infin$，费用为 $0$ 的边；
• 对于满足 $i<j,a_i>a_j$ 的 $i,j$，从 $y_i$ 向 $x_j$ 连流量为 $\infin$，费用为 $0$ 的边。

然后 $k$ 的答案即为 $\sum b_i$ 加上流量 $\le k$ 的最小费用，这个可以通过建虚拟汇点，每次从虚拟汇点向汇点增加一条流量为 $1$，费用为 $0$ 的边即可。

代码如下：

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#include <iostream>
#include <cstdio>
#include <queue>

using namespace std;

const int S=2005,MS=1000005;
const int inf=1e9;

int n,a[S],b[S];
int s,t;
int esum,to[MS],nxt[MS],h[S];
int c[MS],cost[MS],dis[S];
int cur[S];
bool vis[S];
int mincost;

inline void init()
{
	esum=1;
	s=0,t=n*2+2;
	for(int i=s;i<=t;i++) h[i]=0;
}

inline void added(int x,int y,int w,int v)
{
	to[++esum]=y;
	c[esum]=w;
	cost[esum]=v;
	nxt[esum]=h[x];
	h[x]=esum;
}
inline void add(int x,int y,int w,int v)
{
	added(x,y,w,v),added(y,x,0,-v);
}

inline bool spfa()
{
	for(int i=s;i<=t;i++)
	{
		cur[i]=h[i];
		dis[i]=inf;
		vis[i]=false;
	}
	queue<int> q;
	dis[s]=0;
	vis[s]=true;
	q.push(s);
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		vis[u]=false;
		for(int i=h[u];i;i=nxt[i])
		{
			int v=to[i],w=cost[i];
			if(c[i]>0&&dis[u]+w<dis[v])
			{
				dis[v]=dis[u]+w;
				if(!vis[v])
				{
					vis[v]=true;
					q.push(v);
				}
			}
		}
	}
	return dis[t]<inf;
}

int dfs(int u,int w)
{
	if(u==t) return w;
	vis[u]=true;
	int sum=0;
	for(int &i=cur[u];i;i=nxt[i])
	{
		int v=to[i];
		if(c[i]>0&&dis[v]==dis[u]+cost[i]&&!vis[v])
		{
			int re=dfs(v,min(w,c[i]));
			mincost+=re*cost[i];
			c[i]-=re;
			c[i^1]+=re;
			w-=re;
			sum+=re;
			if(w==0) break;
		}
	}
	vis[u]=false;
	return sum;
}

inline int mcmf()
{
	int res=0;
	mincost=0;
	while(spfa()) res+=dfs(s,inf);
	return res;
}

inline void slove()
{
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	int sm=0;
	for(int i=1;i<=n;i++) cin>>b[i],sm+=b[i];
	init();
	for(int i=1;i<=n;i++)
	{
		add(s,i,inf,0);
		add(i,i+n,1,-b[i]);
		add(i+n,n*2+1,inf,0);
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=i+1;j<=n;j++)
		{
			if(a[j]>=a[i]) continue;
			add(i+n,j,inf,0);
		}
	}
	int ans=0;
	for(int i=1;i<=n;i++)
	{
		add(n*2+1,t,1,0);
		mcmf();
		ans+=mincost;
		cout<<sm+ans<<' ';
	}
	cout<<'\n';
}

int main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int T;
	cin>>T;
	while(T-->0) slove();
	return 0;
}