社区讨论
有没有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 条回复,欢迎继续交流。
正在加载回复...