bzoj千题计划141:bzoj3532: [Sdoi2014]Lis

时间:2022-09-16 19:43:03

http://www.lydsy.com/JudgeOnline/problem.php?id=3532

如果没有字典序的限制,那么DP拆点最小割即可

加上字典序的限制:

按c从小到大枚举最小割边集中的边,去掉这条边对网络的影响,继续枚举直至获得最小割边集

判断是不是最小割边集中的边:

在残量网络中边的起点和终点不连通

注:最小割边集中的边一定满流,但满流边不一定是最小割边集中的边

如下图所示,流量为1和3的两条边满流,但最小割边集为流量为4的那条边

bzoj千题计划141:bzoj3532: [Sdoi2014]Lis

去掉一条边对网络的影响:

边:u-->v

这条边的流量和反向弧的流量置为0

在残量网络上,汇点向v跑一遍最大流,u向源点跑一遍最大流

判断已经得到了最小割中的所有边:

残量网络上,源点和汇点不连通

#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm> using namespace std; #define N 1410
#define M 520000
const int inf=2e9; int n;
int a[N],b[N],c[N]; int f[N]; int tot;
int front[N],nxt[M<<],to[M<<],val[M<<],from[M<<];
int lev[N],num[N];
int path[N];
int cur[N]; int src,decc; int id[N];
bool use[N];
int cnt[N]; int all; int ans[N]; bool vis[N]; void read(int &x)
{
x=; char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) { x=x*+c-''; c=getchar(); }
} void add(int u,int v,int w)
{
to[++tot]=v; nxt[tot]=front[u]; front[u]=tot; from[tot]=u; val[tot]=w;
to[++tot]=u; nxt[tot]=front[v]; front[v]=tot; from[tot]=v; val[tot]=;
// cout<<u<<' '<<v<<' '<<w<<'\n';
} bool bfs()
{
queue<int>q;
for(int i=;i<=all;++i) lev[i]=all;
q.push(decc);
lev[decc]=;
int now,t;
while(!q.empty())
{
now=q.front();
q.pop();
for(int i=front[now];i;i=nxt[i])
{
t=to[i];
if(lev[t]==all && val[i^])
{
lev[t]=lev[now]+;
q.push(t);
}
}
}
return lev[src]!=all;
} int augment()
{
int now=decc,flow=inf;
int i;
while(now!=src)
{
i=path[now];
flow=min(flow,val[i]);
now=from[i];
}
now=decc;
while(now!=src)
{
i=path[now];
val[i]-=flow;
val[i^]+=flow;
now=from[i];
}
return flow;
} void isap()
{
int flow=;
if(!bfs()) return ;
memset(num,,sizeof(num));
for(int i=;i<=all;++i) num[lev[i]]++,cur[i]=front[i];
int now=src,t;
while(lev[src]<all)
{
if(now==decc)
{
flow+=augment();
now=src;
}
bool advanced=false;
for(int i=cur[now];i;i=nxt[i])
{
t=to[i];
if(lev[t]==lev[now]- && val[i])
{
advanced=true;
path[t]=i;
cur[now]=i;
now=t;
break;
}
}
if(!advanced)
{
int mi=all;
for(int i=front[now];i;i=nxt[i])
if(val[i]) mi=min(mi,lev[to[i]]);
if(!--num[lev[now]]) break;
num[lev[now]=mi+]++;
cur[now]=front[now];
if(now!=src) now=from[path[now]];
}
}
// cout<<flow<<'\n';
} void build()
{
src=; decc=(n<<|)+;
int mx,max_len=;
for(int i=n;i;--i)
{
mx=;
for(int j=i+;j<=n;++j)
if(a[j]>a[i]) mx=max(mx,f[j]);
f[i]=mx+;
max_len=max(max_len,f[i]);
}
tot=;
memset(front,,sizeof(front));
for(int i=;i<=n;++i)
{
id[i]=tot+;
add(i<<,i<<|,b[i]);
}
for(int i=;i<=n;++i)
if(f[i]==max_len) add(src,i<<,inf);
for(int i=;i<=n;++i)
if(f[i]==) add(i<<|,decc,inf);
for(int i=;i<=n;++i)
for(int j=i+;j<=n;++j)
if(a[j]>a[i] && f[i]==f[j]+) add(i<<|,j<<,inf);
} bool find(int u,int v)
{
memset(vis,false,sizeof(vis));
queue<int>q;
q.push(u);
vis[u]=true;
int now,t;
while(!q.empty())
{
now=q.front();
q.pop();
for(int i=front[now];i;i=nxt[i])
{
if(!val[i]) continue;
t=to[i];
if(!vis[t])
{
vis[t]=true;
q.push(t);
}
}
}
return vis[v];
} void solve()
{
int sum=,num=;
int mi;
c[]=inf;
memset(use,false,sizeof(use));
while()
{
mi=;
for(int i=;i<=n;++i)
if(!val[id[i]] && !use[i] && c[mi]>c[i]) mi=i;
use[mi]=true;
if(find(from[id[mi]],to[id[mi]])) continue;
ans[++num]=mi;
sum+=b[mi];
val[id[mi]]=val[id[mi]+]=;
src=all; decc=mi<<|;
isap();
src=mi<<; decc=;
isap();
src=all; decc=;
if(!bfs()) break;
}
cout<<sum<<' '<<num<<'\n';
sort(ans+,ans+num+);
for(int i=;i<num;++i) cout<<ans[i]<<' ';
cout<<ans[num]<<'\n';
} int main()
{
int T;
read(T);
while(T--)
{
read(n);
all=(n<<|)+;
for(int i=;i<=n;++i) read(a[i]);
for(int i=;i<=n;++i) read(b[i]);
for(int i=;i<=n;++i) read(c[i]);
build();
isap();
solve();
}
}

3532: [Sdoi2014]Lis

Time Limit: 10 Sec  Memory Limit: 512 MB
Submit: 977  Solved: 362
[Submit][Status][Discuss]

Description

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

Input

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

Output

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

Sample Input

1
6
3 4 4 2 2 3
2 1 1 1 1 2
6 5 4 3 2 1

Sample Output

4 3
2 3 6
解释:删去(A2,43,A6),(A1,A6),(A2,43,44,A5)等都是合法的方案,但
{A2,43,A6)对应的C值的字典序最小。

HINT

1 < =N < =700     T < =5

bzoj千题计划141:bzoj3532: [Sdoi2014]Lis的更多相关文章

  1. bzoj千题计划300:bzoj4823&colon; &lbrack;Cqoi2017&rsqb;老C的方块

    http://www.lydsy.com/JudgeOnline/problem.php?id=4823 讨厌的形状就是四联通图 且左右各连一个方块 那么破坏所有满足条件的四联通就好了 按上图方式染色 ...

  2. bzoj千题计划205:bzoj3529&colon; &lbrack;Sdoi2014&rsqb;数表

    http://www.lydsy.com/JudgeOnline/problem.php?id=3529 有一张n*m的数表,其第i行第j列(1 < =i < =n,1 < =j & ...

  3. bzoj千题计划196:bzoj4826&colon; &lbrack;Hnoi2017&rsqb;影魔

    http://www.lydsy.com/JudgeOnline/problem.php?id=4826 吐槽一下bzoj这道题的排版是真丑... 我还是粘洛谷的题面吧... 提供p1的攻击力:i,j ...

  4. bzoj千题计划280:bzoj4592&colon; &lbrack;Shoi2015&rsqb;脑洞治疗仪

    http://www.lydsy.com/JudgeOnline/problem.php?id=4592 注意操作1 先挖再补,就是补的范围可以包含挖的范围 SHOI2015 的题 略水啊(逃) #i ...

  5. bzoj千题计划177:bzoj1858&colon; &lbrack;Scoi2010&rsqb;序列操作

    http://www.lydsy.com/JudgeOnline/problem.php?id=1858 2018 自己写的第1题,一遍过 ^_^ 元旦快乐 #include<cstdio&gt ...

  6. bzoj千题计划317:bzoj4650&colon; &lbrack;Noi2016&rsqb;优秀的拆分(后缀数组&plus;差分)

    https://www.lydsy.com/JudgeOnline/problem.php?id=4650 如果能够预处理出 suf[i] 以i结尾的形式为AA的子串个数 pre[i] 以i开头的形式 ...

  7. bzoj千题计划316:bzoj3173&colon; &lbrack;Tjoi2013&rsqb;最长上升子序列(二分&plus;树状数组)

    https://www.lydsy.com/JudgeOnline/problem.php?id=3173 插入的数是以递增的顺序插入的 这说明如果倒过来考虑,那么从最后一个插入的开始删除,不会对以某 ...

  8. bzoj千题计划304:bzoj3676&colon; &lbrack;Apio2014&rsqb;回文串(回文自动机)

    https://www.lydsy.com/JudgeOnline/problem.php?id=3676 回文自动机模板题 4年前的APIO如今竟沦为模板,,,╮(╯▽╰)╭,唉 #include& ...

  9. bzoj千题计划292:bzoj2244&colon; &lbrack;SDOI2011&rsqb;拦截导弹

    http://www.lydsy.com/JudgeOnline/problem.php?id=2244 每枚导弹成功拦截的概率 = 包含它的最长上升子序列个数/最长上升子序列总个数 pre_len ...

随机推荐

  1. linQ学习笔记之三高级语句

    linq语句查询执行的时机 第一步获取数据源 int [] obejct = new int[]{1,2,3,4,5,6,7,8,9} 第二步定义查询 var even = numbers.where ...

  2. 学习资料 数据查询语言DQL

    数据查询语言DQL介绍及其应用: 查询是SQL语言的核心,SQL语言只提供唯一一个用于数据库查询的语句,即SELECT语句.用于表达SQL查询的SELECT语句是功能最强也是最复杂的SQL语句,它提供 ...

  3. 分布式文件系统FastDFS设计原理

    原文地址: http://blog.chinaunix.net/uid-20196318-id-4058561.html FastDFS是一个开源的轻量级分布式文件系统,由跟踪服务器(tracker ...

  4. android升级软件版本号,您安装后的新版本号,成功安装画面没有出现,或直接回到桌面

    Intent intent = new Intent(Intent.ACTION_VIEW); intent.addFlags(Intent.FLAG_ACTIVITY_NEW_TASK); //an ...

  5. 浅谈Django的生命周期和CBF和FBC

    Django的生命周期和CBF和FBC 对于所有的web框架来说本质就是一个socket服务端,浏览器是socket客户端,客户端和服务端通信,字符串(Http协议):请求头和请求体 响应头+响应体 ...

  6. X5 Blink下文字自动变大

    在X5 Blink中,页面排版时会主动对字体进行放大,会检测页面中的主字体,当某一块的字体在我们的判定规则中,认为字体的字号较小,并且是页面中的主要字体,就会采用主动放大的操作.这显然不是我们想要的. ...

  7. Linux 文件目录解释

    /bin:bin是binary(二进制)的缩写.这个目录是对UNIX系统习惯的沿袭,存放着使用者最经常使用的命令.例如:cp,ls,cat. /boot:这里存放的是启动LINUX时使用的一些核心文件 ...

  8. Scala&lpar;二&rpar; —— 函数

    try 表达式 var result = try{ Integer.parseInt("dog") }catch{ case _ => 0 }finally{ println ...

  9. 生信基础知识【04】GO和pathway分析

    非原创 参考资料: 一文掌握GO和pathway分析 - 生物信息学讨论版 -丁香园论坛http://www.dxy.cn/bbs/thread/34904124#34904124 GO富集 GO是G ...

  10. 通过wlst工具创建weblogic11g域单节点包括服务与被管服务

    1:创建域(1)节点一执行 export MV_HOME=/home/wzh/Oracle/Middleware export WL_HOME=$MV_HOME/wlserver_10. export ...