2019牛客多校第三场 I Median-程序员宅基地

技术标签： DP

题意：输入b[3]...b[n]，表示n,n-1,n-2位置的中位数，求构造一个序列。

题解给出一个结论是如果有解，那么a[i]必可以是可以受他影响的三个中位数中的一个。反证法：如果a[i]不是这三个中的其中一个，简单分析可知，必然有a[i] 大于这三个的最大值或者小于他们的最小值，那么显然把这个值调为最大值或者最小值，不会影响三个中位数。

这样很有道理，就可以DP了，令影响a[i]的三个数字位v[i][0-2]，f[i][j][k]表示a[i]=v[i][j],a[i-1]=v[i-1][k]是否有可行解，于是我们每次枚举f[i][j][k]和f[i-1][k][l]，是否能转移过来的条件就是f[i-1][k][l]=1且mid{v[i][j],v[i-1][k],v[i-2][l]}=b[i]。同时记录是由哪一个l转移过来的，方便最后找出一组解

初始化，必有a[1]=b[3]不会对后面造成任何影响,所以令v[1][0..2]=b[3]，前2位是随便怎样都可行的，f[2][0..2][0..2]=1。

#include<bits/stdc++.h>
#define maxl 100010
using namespace std;

int n;
int b[maxl];
int v[maxl][3],f[maxl][3][3],pre[maxl][3][3];
bool flag;
int ans[maxl];

inline void prework()
{
	scanf("%d",&n);
	for(int i=3;i<=n;i++)
		scanf("%d",&b[i]);
	b[2]=b[1]=b[3];
	b[n+1]=b[n+2]=b[n];
	v[1][0]=v[1][1]=v[1][2]=b[1];
	for(int i=2;i<=n;i++)
		v[i][0]=b[i],v[i][1]=b[i+1],v[i][2]=b[i+2];
	for(int i=1;i<=n;i++)
		sort(v[i],v[i]+2);
}

inline int sorta(int a,int b,int c)
{
	if(a>b) swap(a,b);
    if(a>c) swap(a,c);
    if(b>c) swap(b,c);
    return b;
}

inline void mainwork()
{
	for(int i=1;i<=n;i++)
		for(int j=0;j<3;j++)
			for(int k=0;k<3;k++)
				f[i][j][k]=0,pre[i][j][k]=0;
	for(int j=0;j<3;j++)
		for(int k=0;k<3;k++)
			f[2][j][k]=1;
	for(int i=3;i<=n;i++)
		for(int j=0;j<3;j++)
			for(int k=0;k<3;k++)
				for(int l=0;l<3;l++)
				if(f[i-1][k][l])
				{
					if(sorta(v[i-2][l],v[i-1][k],v[i][j])==b[i])
					{
						f[i][j][k]=1;pre[i][j][k]=l;
						break;
					}
				}
	flag=false;int jj,kk,l;
	for(int j=0;j<3 && !flag;j++)
		for(int k=0;k<3;k++)
		if(f[n][j][k])
		{
			jj=j;kk=k;
			flag=true;
			break;
		}
	if(!flag) return;
	for(int i=n;i>=2;i--)
	{
		ans[i]=v[i][jj];
		l=pre[i][jj][kk];
		jj=kk;kk=l;
	}
	ans[1]=b[1];
}

inline void print()
{
	if(!flag)
		puts("-1");
	else
		for(int i=1;i<=n;i++)
			printf("%d%c",ans[i],(i==n)?'\n':' ');
}

int main()
{
	int t;
	scanf("%d",&t);
	for(int i=1;i<=t;i++)
	{
		prework();
		mainwork();
		print();
	}
	return 0;
}

本文链接：https://blog.csdn.net/liufengwei1/article/details/97392482

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

软件测试流程包括哪些内容？测试方法有哪些？_测试过程管理中包含哪些过程-程序员宅基地

文章浏览阅读2.9k次，点赞8次，收藏14次。测试主要做什么？这完全都体现在测试流程中，同时测试流程是面试问题中出现频率最高的，这不仅是因为测试流程很重要，而是在面试过程中这短短的半小时到一个小时的时间，通过测试流程就可以判断出应聘者是否合适，故在测试流程中包含了测试工作的核心内容，例如需求分析，测试用例的设计，测试执行，缺陷等重要的过程。..._测试过程管理中包含哪些过程

政府数字化政务的人工智能与机器学习应用：如何提高政府工作效率-程序员宅基地

文章浏览阅读870次，点赞16次，收藏19次。1.背景介绍政府数字化政务是指政府利用数字技术、互联网、大数据、人工智能等新技术手段，对政府政务进行数字化改革，提高政府工作效率，提升政府服务质量的过程。随着人工智能(AI)和机器学习(ML)技术的快速发展，政府数字化政务中的人工智能与机器学习应用也逐渐成为政府改革的重要内容。政府数字化政务的人工智能与机器学习应用涉及多个领域，包括政策决策、政府服务、公共安全、社会治理等。在这些领域，人工...

ssm+mysql+微信小程序考研刷题平台_mysql刷题软件-程序员宅基地

文章浏览阅读219次，点赞2次，收藏4次。系统主要的用户为用户、管理员，他们的具体权限如下：用户：用户登录后可以对管理员上传的学习视频进行学习。用户可以选择题型进行练习。用户选择小程序提供的考研科目进行相关训练。用户可以进行水平测试，并且查看相关成绩用户可以进行错题集的整理管理员：管理员登录后可管理个人基本信息管理员登录后可管理个人基本信息管理员可以上传、发布考研的相关例题及其分析，并对题型进行管理管理员可以进行查看、搜索考研题目及错题情况。_mysql刷题软件

根据java代码描绘uml类图_Myeclipse8.5下JAVA代码导成UML类图-程序员宅基地

文章浏览阅读1.4k次。myelipse里有UML1和UML2两种方式，UML2功能更强大，但是两者生成过程差别不大1.建立Test工程，如下图，uml包存放uml类图package com.zz.domain;public class User {private int id;private String name;public int getId() {return id;}public void setId(int..._根据以下java代码画出类图

Flume自定义拦截器-程序员宅基地

文章浏览阅读174次。需求：一个topic包含很多个表信息，需要自动根据json字符串中的字段来写入到hive不同的表对应的路径中。发送到Kafka中的数据原本最外层原本没有pkDay和project，只有data和name。因为担心data里面会空值，所以根同事商量，让他们在最外层添加了project和pkDay字段。pkDay字段用于表的自动分区，proejct和name合起来用于自动拼接hive表的名称为 ..._flume拦截器自定义开发 kafka

java同时输入不同类型数据,Java Spring中同时访问多种不同数据库-程序员宅基地

文章浏览阅读380次。原标题：Java Spring中同时访问多种不同数据库多样的工作要求，可以使用不同的工作方法，只要能获得结果，就不会徒劳。开发企业应用时我们常常遇到要同时访问多种不同数据库的问题，有时是必须把数据归档到某种数据仓库中，有时是要把数据变更推送到第三方数据库中。使用Spring框架时，使用单一数据库是非常容易的，但如果要同时访问多个数据库的话事件就变得复杂多了。本文以在Spring框架下开发一个Sp..._根据输入的不同连接不同的数据库