luogu P5470 [NOI2019]序列 dp 贪心 费用流 模拟费用流

时间：2022-05-16 20:43:33

LINK:序列

考虑前20分 容易想到爆搜。

考虑dp 容易设\(f_{i,j,k,l}\)表示前i个位置 选了j对 且此时A选择了k个 B选择了l个的最大值.期望得分28.

code
//#include<bits/stdc++.h>

#include<iostream>

#include<cstdio>

#include<ctime>

#include<cctype>

#include<queue>

#include<deque>

#include<stack>

#include<iostream>

#include<iomanip>

#include<cstdio>

#include<cstring>

#include<string>

#include<ctime>

#include<cmath>

#include<cctype>

#include<cstdlib>

#include<queue>

#include<deque>

#include<stack>

#include<vector>

#include<algorithm>

#include<utility>

#include<bitset>

#include<set>

#include<map>

#define ll long long

#define db double

#define INF 1000000000

#define ldb long double

#define pb push_back

#define put_(x) printf("%d ",x);

#define get(x) x=read()

#define gt(x) scanf("%d",&x)

#define gi(x) scanf("%lf",&x)

#define put(x) printf("%d\n",x)

#define putl(x) printf("%lld\n",x)

#define rep(p,n,i) for(RE int i=p;i<=n;++i)

#define go(x) for(int i=lin[x],tn=ver[i];i;tn=ver[i=nex[i]])

#define fep(n,p,i) for(RE int i=n;i>=p;--i)

#define vep(p,n,i) for(RE int i=p;i<n;++i)

#define pii pair<int,int>

#define mk make_pair

#define RE register

#define P 1000000007ll

#define gf(x) scanf("%lf",&x)

#define pf(x) ((x)*(x))

#define uint unsigned long long

#define ui unsigned

#define EPS 1e-4

#define sq sqrt

#define F first

using namespace std;

char *fs,*ft,buf[1<<15];

inline char gc()

{

	return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;

}

inline int read()

{

	RE int x=0,f=1;RE char ch=gc();

	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=gc();}

	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=gc();}

	return x*f;

}

const int MAXN=32;

int T,n,K,L;

int a[MAXN],b[MAXN];

ll f[MAXN][MAXN][MAXN][MAXN];

int main()

{

	//freopen("1.in","r",stdin);

	get(T);

	while(T--)

	{

		memset(f,0xcf,sizeof(f));

		get(n);get(K);get(L);

		rep(1,n,i)get(a[i]);

		rep(1,n,i)get(b[i]);

		f[0][0][0][0]=0;

		rep(1,n,i)

		{

			int cc=min(i-1,L);

			rep(0,cc,j)

			{

				int ww=min(i-1,K);

				rep(0,ww,l)rep(0,ww,r)

				{

					if(l+1<=K&&r+1<=K&&j+1<=L)f[i][j+1][l+1][r+1]=max(f[i-1][j][l][r]+a[i]+b[i],f[i][j+1][l+1][r+1]);

					if(l+1<=K&&r+1<=K)f[i][j][l+1][r+1]=max(f[i-1][j][l][r]+a[i]+b[i],f[i][j][l+1][r+1]);

					if(l+1<=K)f[i][j][l+1][r]=max(f[i-1][j][l][r]+a[i],f[i][j][l+1][r]);

					if(r+1<=K)f[i][j][l][r+1]=max(f[i-1][j][l][r]+b[i],f[i][j][l][r+1]);

					f[i][j][l][r]=max(f[i][j][l][r],f[i-1][j][l][r]);

				}

			}

		}

		putl(f[n][L][K][K]);

	}

	return 0;

}

容易发现这可以贪心 考虑费用流.遗憾的是 考场上我建了2h的图没建出来。

最近 我又建了1h图 还是没有什么进展 看完题解的建图恍然大悟.

我一直考虑把限制少的先建立出来 把限制多的放后边加边来进行限制。

其实并非如此.先考虑 将限制多的先建立出来.

即先限流L 然后流向每个i点流量费用\((1,A[i])\) 然后 i+n\((1,B[i])\) 然后 i向i+n连边。

接下来处理那些随便流的。i连向一个公共点cc 然限流 cc-zz (K-L,0) zz连向i+n的那些点即可.

期望的分64?实际得分48.

code
//#include<bits/stdc++.h>

#include<iostream>

#include<cstdio>

#include<ctime>

#include<cctype>

#include<queue>

#include<deque>

#include<stack>

#include<iostream>

#include<iomanip>

#include<cstdio>

#include<cstring>

#include<string>

#include<ctime>

#include<cmath>

#include<cctype>

#include<cstdlib>

#include<queue>

#include<deque>

#include<stack>

#include<vector>

#include<algorithm>

#include<utility>

#include<bitset>

#include<set>

#include<map>

#define ll long long

#define db double

#define INF 10000000000000000ll

#define inf 1000000000

#define ldb long double

#define pb push_back

#define put_(x) printf("%d ",x);

#define get(x) x=read()

#define gt(x) scanf("%d",&x)

#define gi(x) scanf("%lf",&x)

#define put(x) printf("%d\n",x)

#define putl(x) printf("%lld\n",x)

#define rep(p,n,i) for(RE int i=p;i<=n;++i)

#define go(x) for(int i=lin[x],tn=ver[i];i;tn=ver[i=nex[i]])

#define fep(n,p,i) for(RE int i=n;i>=p;--i)

#define vep(p,n,i) for(RE int i=p;i<n;++i)

#define pii pair<int,int>

#define mk make_pair

#define RE register

#define P 1000000007ll

#define gf(x) scanf("%lf",&x)

#define pf(x) ((x)*(x))

#define uint unsigned long long

#define ui unsigned

#define EPS 1e-4

#define sq sqrt

#define S second

#define F first

using namespace std;

char *fs,*ft,buf[1<<15];

inline char gc()

{

	return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;

}

inline int read()

{

	RE int x=0,f=1;RE char ch=gc();

	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=gc();}

	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=gc();}

	return x*f;

}

const int MAXN=200010,N=MAXN<<1,maxn=MAXN*5<<1;

int n,m,T,TT,zz,cc,S,SS,K,L,len;

int a[MAXN],b[MAXN],in[N],vis[N],pre[N];ll dis[N],ans;

int lin[N],ver[maxn],e[maxn],e1[maxn],nex[maxn],q[maxn<<1];

inline void add(int x,int y,int z,int z1)

{

	ver[++len]=y;nex[len]=lin[x];lin[x]=len;e[len]=z;e1[len]=z1;

	ver[++len]=x;nex[len]=lin[y];lin[y]=len;e[len]=0;e1[len]=-z1;

}

inline bool spfa()

{

	rep(1,T,i)dis[i]=-INF;

	dis[S]=0;in[S]=inf;int l=0,r;

	q[r=1]=S;vis[S]=1;

	//cout<<l<<endl;

	while(++l<=r)

	{

		int x=q[l];vis[x]=0;

		go(x)

		{

			if(!e[i])continue;

			//cout<<tn<<endl;

			if(dis[tn]<dis[x]+e1[i])

			{

				dis[tn]=dis[x]+e1[i];

				if(!vis[tn])q[++r]=tn,vis[tn]=1;

				in[tn]=min(in[x],e[i]);

				pre[tn]=i;

			}

		}

	}

	//cout<<dis[T]<<endl;

	return dis[T]!=-INF;

}

inline void EK()

{

	ans=0;

	//cout<<1<<endl;

	while(spfa())

	{

		int x=T,i=pre[x];

		ans+=dis[T]*in[T];

		while(x!=S)

		{

			e[i]-=in[T];

			e[i^1]+=in[T];

			x=ver[i^1];i=pre[x];

		}

	}

}

int main()

{

	//freopen("1.in","r",stdin);

	get(TT);

	while(TT--)

	{

		rep(1,T,i)lin[i]=0;len=1;

		get(n);get(K);get(L);

		rep(1,n,i)get(a[i]);

		rep(1,n,i)get(b[i]);

		zz=n<<1|1;cc=zz+1;S=cc+1;SS=S+1;T=SS+1;

		add(S,SS,K,0);

		add(zz,cc,K-L,0);

		rep(1,n,i)

		{

			add(i,i+n,1,0);

			add(i,zz,1,0);

			add(SS,i,1,a[i]);

			add(cc,i+n,1,0);

			add(i+n,T,1,b[i]);

		}

		//cout<<len<<endl;

		EK();putl(ans);

	}

	return 0;

}

考虑正解 费用流是正确的 不过复杂度太高了 没有保证.

我们可以进行模拟费用流来将复杂度降下来。

所以操作都模拟费用流时 优先跑增广路的权值最大的即可.

其中有些细节：因为退流的操作很难模拟出来,所以我们考虑当退流的时候 其实是选择一个和其匹配的点.

综上 我们这个模拟费用流不退流 每个被选择的数字都是最终的答案的一部分.

操作：显然应该先选出K-L的*流.

然后考虑三种情况 一种是a[x]+b[x] 一种是给已经选了A[x]的但没有选B[x]的配一个B[x]以及剩下的A中的最大值.

还有一种和前者相反 讨论清楚 开堆模拟即可.

容易证明复杂度为\(nlogn\)

code
//#include<bits/stdc++.h>

#include<iostream>

#include<cstdio>

#include<ctime>

#include<cctype>

#include<queue>

#include<deque>

#include<stack>

#include<iostream>

#include<iomanip>

#include<cstdio>

#include<cstring>

#include<string>

#include<ctime>

#include<cmath>

#include<cctype>

#include<cstdlib>

#include<queue>

#include<deque>

#include<stack>

#include<vector>

#include<algorithm>

#include<utility>

#include<bitset>

#include<set>

#include<map>

#define ll long long

#define db double

#define INF 10000000000000000ll

#define inf 1000000000

#define ldb long double

#define pb push_back

#define put_(x) printf("%d ",x);

#define get(x) x=read()

#define gt(x) scanf("%d",&x)

#define gi(x) scanf("%lf",&x)

#define put(x) printf("%d\n",x)

#define putl(x) printf("%lld\n",x)

#define rep(p,n,i) for(RE int i=p;i<=n;++i)

#define go(x) for(int i=lin[x],tn=ver[i];i;tn=ver[i=nex[i]])

#define fep(n,p,i) for(RE int i=n;i>=p;--i)

#define vep(p,n,i) for(RE int i=p;i<n;++i)

#define pii pair<int,int>

#define mk make_pair

#define RE register

#define P 1000000007ll

#define gf(x) scanf("%lf",&x)

#define pf(x) ((x)*(x))

#define uint unsigned long long

#define ui unsigned

#define EPS 1e-4

#define sq sqrt

#define S second

#define F first

using namespace std;

char *fs,*ft,buf[1<<15];

inline char gc()

{

	return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;

}

inline int read()

{

	RE int x=0,f=1;RE char ch=gc();

	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=gc();}

	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=gc();}

	return x*f;

}

const int MAXN=200010,N=MAXN<<1,maxn=MAXN*5<<1;

int n,m,K,L,T;ll ans=0;

int a[MAXN],b[MAXN],id[MAXN],s[MAXN];

struct A{int id;inline bool friend operator <(A x,A y){return a[x.id]<a[y.id];}}w1;

struct B{int id;inline bool friend operator <(B x,B y){return b[x.id]<b[y.id];}}w2;

struct AB{int id;inline bool friend operator <(AB x,AB y){return a[x.id]+b[x.id]<b[y.id]+a[y.id];}}w3;

priority_queue<A>H1,F1;

priority_queue<B>H2,F2;

priority_queue<AB>H3;

inline int cmpa(int x,int y){return a[x]>a[y];}

inline int cmpb(int x,int y){return b[x]>b[y];}

inline void solve(int m)

{

	rep(1,n,i)id[i]=i;ans=0;

	sort(id+1,id+1+n,cmpa);rep(1,m,i)ans+=a[id[i]],s[id[i]]=1;

	sort(id+1,id+1+n,cmpb);rep(1,m,i)ans+=b[id[i]],s[id[i]]|=2;

}

int main()

{

	//freopen("1.in","r",stdin);

	get(T);

	while(T--)

	{

		get(n);get(K);get(L);

		rep(1,n,i)get(a[i]),s[i]=0;

		rep(1,n,i)get(b[i]);

		while(H1.size())H1.pop();

		while(H2.size())H2.pop();

		while(H3.size())H3.pop();

		while(F1.size())F1.pop();

		while(F2.size())F2.pop();

		solve(K-L);

		int res=0;

		rep(1,n,i)

		{

			if(s[i]==3){++res;continue;}

			if(!s[i])

			{

				w1.id=i;H1.push(w1);

				w2.id=i;H2.push(w2);

				w3.id=i;H3.push(w3);

			}

			if(s[i]==1)w2.id=i,H2.push(w2),F2.push(w2);

			if(s[i]==2)w1.id=i,H1.push(w1),F1.push(w1);

		}

		int id1,id2,v1,v2,v3,c1,c2,mx;

		while(L--)

		{

			while(H1.size()&&(s[H1.top().id]&1))H1.pop();

			while(F1.size()&&(s[F1.top().id]&1))F1.pop();

			while(H2.size()&&(s[H2.top().id]&2))H2.pop();

			while(F2.size()&&(s[F2.top().id]&2))F2.pop();

			while(H3.size()&&s[H3.top().id])H3.pop();

			if(res)

			{

				--res;

				id1=H1.top().id,id2=H2.top().id;

				ans+=a[id1];ans+=b[id2];

				s[id1]|=1;s[id2]|=2;

				if(id1==id2){++res;continue;}

				if(s[id1]==3)++res;

				if(s[id2]==3)++res;

				if(s[id1]==1)w2.id=id1,F2.push(w2);

				if(s[id2]==2)w1.id=id2,F1.push(w1);

				continue;

			}

			v1=0,v2=0,v3=0;

			if(F1.size()){id2=H2.top().id;v1=a[F1.top().id]+b[id2],c1=id2==1?1:0;}

			if(F2.size()){id1=H1.top().id;v2=a[id1]+b[F2.top().id],c2=id1==2?1:0;}

			if(H3.size()){id1=H3.top().id;v3=a[id1]+b[id1];}

			mx=max(max(v1,v2),v3);

			if(v1==v2&&v2==mx)

			{

				if(c1>=c2)

				{

					id2=H2.top().id;id1=F1.top().id;

					ans+=a[id1]+b[id2];

					s[id1]|=1;s[id2]|=2;

					if(s[id2]==3)++res;

					else w1.id=id2,F1.push(w1);

				}

				else

				{

					id1=H1.top().id;id2=F2.top().id;

					ans+=a[id1]+b[id2];

					s[id1]|=1;s[id2]|=2;

					if(s[id1]==3)++res;

					else w2.id=id1,F2.push(w2);

				}

				continue;

			}

			if(v1==mx)

			{

				id2=H2.top().id;id1=F1.top().id;

				ans+=a[id1]+b[id2];

				s[id1]|=1;s[id2]|=2;

				if(s[id2]==3)++res;

				else w1.id=id2,F1.push(w1);

				continue;

			}

			if(v2==mx)

			{

				id1=H1.top().id;id2=F2.top().id;

				ans+=a[id1]+b[id2];

				s[id1]|=1;s[id2]|=2;

				if(s[id1]==3)++res;

				else w2.id=id1,F2.push(w2);

				continue;

			}

			if(mx==v3)

			{

				id1=H3.top().id;

				s[id1]=3;ans+=mx;

				continue;

			}

		}

		putl(ans);

	}

	return 0;

}

luogu P5470 [NOI2019]序列 dp 贪心 费用流 模拟费用流的更多相关文章

  1. Luogu P5470 &lbrack;NOI2019&rsqb;序列

    题目 可以直接贪心,但是用模拟费用流推的话会更轻松. 首先有一个显然的建图方式: \(S\)到\(0\)流量为\(k\),费用为\(0\). \(0\)到\(a_i\)流量为\(1\),费用为\(-a ...

  2. 【题解】Luogu P5470 &lbrack;NOI2019&rsqb;序列

    原题传送门 同步赛上我一开始想了个看似正确却漏洞百出的贪心:按\(a_i+b_i\)的和从大向小贪心 随便想想发现是假的,然后就写了个28pts的暴力dp 杜神后半程说这题就是个贪心,但我没时间写了 ...

  3. 洛谷 P5470 - &lbrack;NOI2019&rsqb; 序列（反悔贪心）

    洛谷题面传送门 好几天没写题解了,写篇题解意思一下(大雾 考虑反悔贪心,首先我们考虑取出 \(a,b\) 序列中最大的 \(k\) 个数,但这样并不一定满足交集 \(\ge L\) 的限制,因此我们需 ...

  4. 【BZOJ-1046】上升序列 DP &plus; 贪心

    1046: [HAOI2007]上升序列 Time Limit: 10 Sec  Memory Limit: 162 MBSubmit: 3723  Solved: 1271[Submit][Stat ...

  5. Luogu P5469 &lbrack;NOI2019&rsqb;机器人 &lpar;DP、多项式&rpar;

    不用FFT的多项式(大雾) 题目链接: https://www.luogu.org/problemnew/show/P5469 (这题在洛谷都成绿题了海星) 题解: 首先我们考虑,一个序列位置最右边的 ...

  6. 51nod 1510 最小化序列 &vert; DP 贪心

    题目描述 现在有一个长度为n的数组A,另外还有一个整数k.数组下标从1开始. 现在你需要把数组的顺序重新排列一下使得下面这个的式子的值尽可能小. ∑|A[i]−A[i+k]| 特别的,你也可以不对数组 ...

  7. &lbrack;BZOJ1046&rsqb;&lbrack;HAOI2007&rsqb;上升序列 DP&plus;贪心

    题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1046 我们先求出对于每一个数字作为开头的LCS的长度f[i],最长的f[i]为mxlen. ...

  8. &lbrack;NOI2019&rsqb;序列（模拟费用流）

    题意: 有两个长度为n的序列,要求从每个序列中选k个,并且满足至少有l个位置都被选,问总和最大是多少. \(1\leq l\leq k\leq n\leq 2*10^5\). 首先,记录当前考虑到的位 ...

  9. 模拟费用流 &amp&semi; 可撤销贪心

    1. CF730I Olympiad in Programming and Sports 大意: $n$个人, 第$i$个人编程能力$a_i$, 运动能力$b_i$, 要选出$p$个组成编程队, $s ...

随机推荐

  1. UML图中经常用到几种的关系图例

    学习这个东西挺奇怪的,时间一长就容易忘记,或者记不清楚.今天看到一些UML图的关系,发现有些出入了,索性就写下来,以后再忘记的时候过来看看. 在UML的类图中,常见的有以下几种关系: 继承(Gener ...

  2. 在Window的IIS中创建FTP的Site并用C&num;进行文件的上传下载

    文件传输协议 (FTP) 是一个标准协议,可用来通过 Internet 将文件从一台计算机移到另一台计算机. 这些文件存储在运行 FTP 服务器软件的服务器计算机上. 然后,远程计算机可以使用 FTP ...

  3. js之字面量、对象字面量的访问、关键字in的用法

    一:字面量含义 字面量表示如何表达这个值,一般除去表达式,给变量赋值时,等号右边都可以认为是字面量. 字面量分为字符串字面量(string literal ).数组字面量(array literal) ...

  4. BZOJ2818&colon; Gcd 欧拉函数求前缀和

    给定整数N,求1<=x,y<=N且Gcd(x,y)为素数的数对(x,y)有多少对. 如果两个数的x,y最大公约数是z,那么x/z,y/z一定是互质的 然后找到所有的素数,然后用欧拉函数求一 ...

  5. js调用打印机

    <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/ ...

  6. Design Pattern Memo 备忘录设计模式

    本设计模式就是简单地记录当前状态.然后利用记录的数据恢复. 比方首先我们有一个类.类须要记录当前状态进行相关的工作的: class Memo; class Human { public: string ...

  7. IntelliJ Idea中一个编译报错引发的

    package verify; public class Verifier { private String name; public Verifier() { this.name = getClas ...

  8. 高效sql2005分页存储过程

    高效分页存储过程 --分页存储过程示例 Alter PROCEDURE [dbo].[JH_PageDemo] @pageSize int = 9000000000, @pageIndex int = ...

  9. 40&period; Combination Sum II&lpar;midum&comma; backtrack&comma; 重要&rpar;

    Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in ...

  10. UML图之时序图

    时序图(Sequence Diagram)是显示对象之间交互的图,这些对象是按时间顺序排列的.顺序图中显示的是参与交互的对象及其对象之间消息交互的顺序.时序图中包括的建模元素主要有:角色(Actor) ...

相关文章