【Codeforces Round #522 C - Playing Piano】爆搜+剪枝

C. Playing Piano

题意

给你一个a数组，让你按照规则构造b数组
规则如下
如果$a_i<a_{i+1}$那么$b_i<b_{i+1}$
如果$a_i>a_{i+1}$那么$b_i>b_{i+1}$
如果$a_i=a_{i+1}$那么$b_i!=b_{i+1}$
给出b数组或者输出-1表示b数组不存在。

做法
考虑一下会发现只有两种情况会出现-1

第一种：连续上升/下降的个数>=6个
第二种：连续五个上升/下降，连续五个下降/上升
先用枚举的方法处理掉-1的情况
不是-1的情况一定是有很多解的，直接爆搜61ms就过掉了。
目前不清楚能不能卡掉爆搜。

代码

#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
const int maxn = 1e5+5;
int a[maxn];
int b[maxn];
int n,ok;
void dfs(int pos)
{
    if(ok==1) return ;if(pos==1){
    for(int i=1;i<=5;i++){
    b[pos]=i;dfs(pos+1);if(ok==1) return;}}else if(pos==n+1){
    ok=1;return ;}else{
    if(a[pos]==a[pos-1]){
    for(int i=1;i<=5;i++){
    if(b[pos-1]!=i){
    b[pos]=i;dfs(pos+1);if(ok) return ;}}}else if(a[pos]<a[pos-1]){
    for(int i=b[pos-1]-1;i>=1;i--){
    b[pos]=i;dfs(pos+1);if(ok) return ;}}else{
    for(int i=b[pos-1]+1;i<=5;i++){
    b[pos]=i;dfs(pos+1);if(ok) return ;}}}
}
int main()
{
    scanf("%d",&n);for(int i=1;i<=n;i++){
    scanf("%d",&a[i]);}if(n==1){
    printf("1\n");return 0;}if(n==2){
    if(a[1]<=a[2]) printf("1 2\n");else if(a[1]>a[2]) printf("2 1\n");return 0;}for(int i=1;i<=n-5;i++)//判断1 2 3 4 5 6{
    int flag=0;for(int j=i;j<=i+4;j++){
    if(a[j]>=a[j+1]) flag=1;}if(flag==0){
    printf("-1\n");return 0;}}for(int i=1;i<=n-5;i++)//判断6 5 4 3 2 1{
    int flag=0;for(int j=i;j<=i+4;j++){
    if(a[j]<=a[j+1]) flag=1;}if(flag==0){
    printf("-1\n");return 0;}}for(int i=1;i<=n-9;i++)//判断1 2 3 4 5 5 4 3 2 1{
    int flag=0;for(int j=i;j<=i+3;j++){
    if(a[j]>=a[j+1]) flag=1;}if(a[i+4]!=a[i+5]) flag=1;for(int j=i+5;j<=i+8;j++){
    if(a[j]<=a[j+1]) flag=1;}if(flag==0){
    if(flag==0){
    printf("-1\n");return 0;}}}for(int i=1;i<=n-9;i++)//判断5 4 3 2 1 1 2 3 4 5{
    int flag=0;for(int j=i;j<=i+3;j++){
    if(a[j]<=a[j+1]) flag=1;}if(a[i+4]!=a[i+5]) flag=1;for(int j=i+5;j<=i+8;j++){
    if(a[j]>=a[j+1]) flag=1;}if(flag==0){
    if(flag==0){
    printf("-1\n");return 0;}}}dfs(1);for(int i=1;i<=n;i++) printf("%d ",b[i]);return 0;
}