社区讨论

有没有dalao帮忙卡下常啊....QwQ

P3308[SDOI2014] LIS参与者 8已保存回复 11

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
11 条
当前快照
1 份
快照标识符
@mi7ylnqo
此快照首次捕获于
2025/11/21 05:44
4 个月前
此快照最后确认于
2025/11/21 06:44
4 个月前
查看原帖
RT
真的过不去了....求开大时限QwQ
CPP
#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<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#define INF 0x3f3f3f3f
using namespace std;
int h[1405],d[1405],dp[705],a[705],b[705],f[705],cnt,S,T,n,m,t,ans,N;
struct wf{int to,nxt,w;}edge[140005<<3];
struct wff{int w,pos;}c[705];
queue<int> Q;
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
void add(int u,int v,int w){
    edge[++cnt].to=v;edge[cnt].w=w;edge[cnt].nxt=h[u];h[u]=cnt;swap(u,v);w=0;
    edge[++cnt].to=v;edge[cnt].w=w;edge[cnt].nxt=h[u];h[u]=cnt;
}
bool bfs(int S,int T)
{
    memset(d,-1,sizeof (d));d[S]=0;Q.push(S);while(!Q.empty()){int u=Q.front();Q.pop();
    for (int i=h[u];i;i=edge[i].nxt){int v=edge[i].to;if (!edge[i].w) continue;if (d[v]==-1){d[v]=d[u]+1;Q.push(v);}}}
    return (d[T]!=-1);
}
int dfs(int u,int T,int a){
    if (u==T||a==0) return a;int left=0,used=0;
    for (int i=h[u];i;i=edge[i].nxt){int v=edge[i].to;
    if (d[v]!=d[u]+1) continue;left=dfs(v,T,min(edge[i].w,a-used));
    used+=left;edge[i].w-=left;edge[i^1].w+=left;if (a==used) return a;}
    if (used==0) d[u]=-1;return used;
}
int dinic(int S,int T){int num=0;while(bfs(S,T))num+=dfs(S,T,INF);return num;}
bool cmp(wff a,wff b){return a.w<b.w;}
int main()
{
	t=read();
	for (int qqq=1;qqq<=t;++qqq)
	{
		n=read();
		cnt=1;memset(h,0,sizeof (h));S=0;T=n<<1|1;N=0;
		for (int i=1;i<=n;++i)a[i]=read();
		for (int i=1;i<=n;++i)b[i]=read();
		for (int i=1;i<=n;++i){c[i].w=read();c[i].pos=i;}
		for (int i=1;i<=n;++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=0;
		for (int i=1;i<=n;++i)ans=max(ans,dp[i]);   
		for (int i=1;i<=n;++i)add(i,i+n,b[i]);
		for (int i=1;i<=n;++i)if(dp[i]==1)add(S,i,INF);
		for (int i=1;i<=n;++i)if(dp[i]==ans)add(i+n,T,INF);
		for (int i=1;i<=n;++i)for (int j=1;j<i;j++)if (dp[i]==dp[j]+1&&a[j]<a[i]) add(j+n,i,INF);
		printf("%d ",dinic(S,T));
		sort(c+1,c+n+1,cmp);
		for (int i=1;i<=n;++i){int u=c[i].pos,v=u+n;
		if (bfs(u,v)) continue;f[++N]=u;dinic(u,S),dinic(T,v);}
		sort(f+1,f+N+1);
		printf("%d\n",N);
		for (int i=1;i<=N;++i)printf("%d ",f[i]);
		printf("\n");
	}
	return 0;
}
你谷神仙多,求指教QwQ

回复

11 条回复,欢迎继续交流。

正在加载回复...