首页 > 代码库 > [SDOI2014]LIS

[SDOI2014]LIS

2024-09-04 18:33:57   219人阅读

 

题目描述

 

给定序列A，序列中的每一项Ai有删除代价Bi和附加属性Ci。请删除若干项，使得4的最长上升子序列长度减少至少1，且付出的代价之和最小，并输出方案。 如果有多种方案，请输出将删去项的附加属性排序之后，字典序最小的一种。

 

输入输出格式

输入格式：

 

 

输入包含多组数据。 输入的第一行包含整数T，表示数据组数。接下来4*T行描述每组数据。 每组数据的第一行包含一个整数N，表示A的项数，接下来三行，每行N个整数A1．．An，B1．，Bn，C1．．Cn，满足1 < =Ai，Bi，Ci < =10^9，且Ci两两不同。

 

 

输出格式：

 

 

对每组数据，输出两行。第一行包含两个整数S，M，依次表示删去项的代价和与数量；接下来一行M个整数，表示删去项在4中的的位置，按升序输出。

 

 

 

输入输出样例

 

输入样例#1：
163 4 4 2 2 32 1 1 1 1 26 5 4 3 2 1
输出样例#1：
4 3    2 3 6解释：删去(A2，43，A6)，(A1，A6)，(A2，43，44，A5)等都是合法的方案，但{A2，43，A6)对应的C值的字典序最小。

 

说明

 

1 < =N < =700 T < =5

 

题意：
给定一个序列，删去若干项，使得序列的 LIS 长度减少，且代价和最小
输出字典序最小的方案

分析：

 技术分享

 

技术分享

技术分享

 

#include<cstdio>#include<cstring>#include<algorithm>#include<iostream>using namespace std;#define FRE(name) freopen(#name".in","r",stdin);freopen(#name".out","w",stdout);const int N=10005;const int inf=0x3f3f3f3f;struct edge{int v,next,cap;}e[N*100];int tot=1,head[N];struct node{int c,id;}c[N];int dis[N],q[N*10];int n,cas,maxflow,maxn,a[N],b[N],f[N],ans[N*10];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;}inline bool cmp(const node &x,const node &y){    return x.c<y.c;}inline void add(int x,int y,int z){    e[++tot].v=y;e[tot].cap=z;e[tot].next=head[x];head[x]=tot;    e[++tot].v=x;e[tot].cap=0;e[tot].next=head[y];head[y]=tot;}inline bool bfs(int S,int T){    memset(dis,-1,sizeof dis);    unsigned short h=0,t=1;    q[t]=S;dis[S]=0;    while(h!=t){        int x=q[++h];        for(int i=head[x];i;i=e[i].next){            if(e[i].cap && dis[e[i].v]==-1){                dis[e[i].v]=dis[x]+1;                if(e[i].v==T) return 1;                q[++t]=e[i].v;            }        }    }    return 0;}int dfs(int x,int T,int f){    if(x==T) return f;    int used=0,t;    for(int i=head[x];i;i=e[i].next){        if(e[i].cap && dis[e[i].v]==dis[x]+1){            t=dfs(e[i].v,T,min(e[i].cap,f));            e[i].cap-=t;e[i^1].cap+=t;            used+=t;f-=t;            if(!f) return used;        }    }    if(!used) dis[x]=-1;    return used;}inline int dinic(int S,int T){    int res=0;    while(bfs(S,T)) res+=dfs(S,T,inf);    return res;}void mapping(int S,int T){    for(int i=1;i<=n;i++) add(i,i+n,b[i]);    for(int i=1;i<=n;i++) if(f[i]==1) add(S,i,inf);    for(int i=1;i<=n;i++) if(f[i]==maxn) add(i+n,T,inf);    for(int i=1;i<=n;i++){        for(int j=1;j<i;j++){            if(a[j]<a[i] && f[i]==f[j]+1){                add(j+n,i,inf);            }        }    }}inline void Cl(){    tot=1;maxn=0;    memset(head,0,sizeof head);}int main(){    //FRE(lis)    for(cas=read();cas--;){        n=read();Cl();        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].c=read(),c[i].id=i;        for(int i=1;i<=n;i++){            f[i]=1;            for(int j=1;j<i;j++){                if(a[j]<a[i]) f[i]=max(f[i],f[j]+1);            }            maxn=max(maxn,f[i]);        }        int S=0,T=n<<1|1,cnt=0;        mapping(S,T);        maxflow=dinic(S,T);        sort(c+1,c+n+1,cmp);        for(int i=1;i<=n;i++){            int now=c[i].id;            int u=now,v=now+n;            if(bfs(u,v)) continue;            dinic(T,v);dinic(u,S);            ans[++cnt]=now;        }        sort(ans+1,ans+cnt+1);        printf("%d %d\n",maxflow,cnt);        for(int i=1;i<cnt;i++) printf("%d ",ans[i]);printf("%d\n",ans[cnt]);    }    return 0;}

 

[SDOI2014]LIS


联系
我们