Codeforces 1079C Playing Piano（记忆化搜索）

题目链接：Playing Piano

题意：给定长度为n的序列$a_i$，要求得到同样长度的序列$b_i$。满足一下条件：

if $a_i < a_{i+1}$ then $b_i < b_{i+1}$

if $a_i > a_{i+1}$ then $b_i > b_{i+1}$

if $a_i = a_{i+1}$ then $b_i  eq b_{i+1}$

$1 <= b_i <= 5$

题解：第一个数从1-5枚举，接着从下一位开始搜索，dp[i][j]表示第i位数字为j的情况是否已经搜索过。

当$a_i<a_{i+1}$的时候，从当前值往后搜索；当$a_i>a_{i+1}$的时候，从当前值往前搜索；$a_i=a_{i+1}$的时候，搜索和当前值不相同的值。搜索的区间范围为1-5。

#include <cstdio>
#include <cstdlib>
using namespace std;

const int N=1e5+10;
int n,a[N],b[N],dp[N][10];

void dfs(int x,int val){
    if(x>n){
        printf("%d",b[1]);
        for(int i=2;i<=n;i++) printf(" %d",b[i]);
        printf("
");
        exit(0);
    }
    if(dp[x][val]) return ;
    dp[x][val]=1;
    if(a[x]>a[x-1]){
        for(int i=val+1;i<=5;i++){
            b[x]=i;
            dfs(x+1,i);
        }
    }
    else if(a[x]<a[x-1]){
        for(int i=1;i<=val-1;i++){
            b[x]=i;
            dfs(x+1,i);
        }
    }
    else{
        for(int i=1;i<=5;i++){
            if(i!=val){
                b[x]=i;
                dfs(x+1,i);
            }
        }
    }
}

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=5;i++){
        b[1]=i;
        dfs(2,i);
    }
    printf("-1
");
    return 0;
}