「SDOI2014」Lis

题目描述

给定序列 \(A\)，序列中的每一项 \(A_i\) 有删除代价 \(B_i\) 和附加属性 \(C_i\)。

请删除若干项，使得 \(A\) 的最长上升子序列长度减少至少 \(1\)，且付出的代价之和最小，并输出方案。

如果有多种方案，请输出将删去项的附加属性排序之后，字典序最小的一种。

\(T\le 5,1\le n\le 700,1\le A_i,B_i,C_i\le 10^9\)

---

上午想这个题的时候，有一种迷之直觉，让我去做网络流24题的最长不下降子序列那题，然后我就去了，然后建模果然是一样的，太神奇啦

按\(dp\)值把点分层，然后把入度为\(0\)的和\(s\)连，把出度为\(0\)的和\(t\)连，发现问题转化成割掉权值和最小的点，使\(s,t\)不连通，可以用拆点最小割做。

然后考虑如何做字典序最小，我们可以从小到大枚举\(C\)，看这条边可不可以成为最小割上的边。

一条边可以是割集上的边\((u,v)\)得在残余网络上满足

• 已经流满了
• \(u\)不可以通过残余网络到\(v\)

可以从\(s\)遍历一遍看看\(u,v\)是否都被遍历或者都没被遍历。

然而这个题在枚举这个边合法后得钦定它，所以得删了它重新建图重新跑，但这肯定不能搞。

考虑一个退流操作，如果在残余网络上删去边\((u,v)\)，可以先跑两边最大流\((t,v)\)和\((u,s)\)的，然后把这条边流量清空，这样复杂度就是对的了（

---

Code:

#include <cstdio>

#include <cctype>

#include <cstring>

#include <algorithm>

using std::min;

using std::max;

int read()

{

	int x=0;char c=getchar();

	while(!isdigit(c)) c=getchar();

	while(isdigit(c)) x=x*10+c-'0',c=getchar();

	return x;

}

const int N=1500;

const int M=3e5;

const int inf=0x3f3f3f3f;

int head[N],to[M],Next[M],edge[M],cnt;

void add(int u,int v,int w)

{

	to[++cnt]=v,edge[cnt]=w,Next[cnt]=head[u],head[u]=cnt;

	to[++cnt]=u,edge[cnt]=0,Next[cnt]=head[v],head[v]=cnt;

}

int q[N],dep[N],l,r;

bool bfs(int s,int t)

{

	memset(dep,0,sizeof dep);

	dep[q[l=r=1]=s]=1;

	while(l<=r)

	{

		int now=q[l++];

		for(int v,i=head[now];i;i=Next[i])

			if(edge[i]&&!dep[v=to[i]])

			{

				dep[v]=dep[now]+1;

				if((q[++r]=v)==t) return true;

			}

	}

	return false;

}

int dfs(int now,int flow,int t)

{

	if(now==t) return flow;

	int res=flow,yuu;

	for(int v,i=head[now];i&&res;i=Next[i])

		if(edge[i]&&dep[v=to[i]]==dep[now]+1)

		{

			yuu=dfs(v,min(res,edge[i]),t);

			if(!yuu){dep[v]=0;continue;}

			edge[i]-=yuu,edge[i^1]+=yuu;

			res-=yuu;

		}

	return flow-res;

}

int Dinic(int s,int t)

{

	int ret=0,flow;

	while(bfs(s,t)) while(flow=dfs(s,inf,t)) ret+=flow;

	return ret;

}

int dp[N],sta[N],tot,a[N];

struct node

{

	int id,x;

	bool friend operator <(node a,node b){return a.x<b.x;}

}yuu[N];

void work()

{

	cnt=1;memset(head,0,sizeof head);

	int n=read(),ans=0;

	for(int i=1;i<=n;i++)

	{

		a[i]=read();

		yuu[i].id=i;

		dp[i]=1;

		for(int j=1;j<i;j++)

			if(a[j]<a[i])

				dp[i]=max(dp[i],dp[j]+1);

		ans=max(ans,dp[i]);

	}

	for(int i=1;i<=n;i++)

		add(i,i+n,read());

	int s=n<<1|1,t=s+1;

	for(int i=1;i<=n;i++)

	{

		yuu[i].x=read();

		if(dp[i]==1) add(s,i,inf);

		if(dp[i]==ans) add(i+n,t,inf);

		for(int j=1;j<i;j++)

			if(a[j]<a[i]&&dp[j]+1==dp[i])

				add(j+n,i,inf);

	}

	printf("%d ",Dinic(s,t));

	std::sort(yuu+1,yuu+1+n);

	for(int i=1;i<=n;i++)

	{

		int u=yuu[i].id;

		if(edge[u<<1]||bfs(u,u+n)) continue;

		sta[++tot]=u;

		Dinic(u,s),Dinic(t,u+n);

		edge[u<<1]=edge[u<<1|1]=0;

	}

	std::sort(sta+1,sta+1+tot);

	printf("%d\n",tot);

	for(int i=1;i<=tot;i++) printf("%d ",sta[i]);

}

int main()

{

	int T=read();

	while(T--) work();

	return 0;

}

---

2019.2.21