【 Codeforces Round #522 C. Playing Piano】 DP+记录路径

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之后爆搜的做法，但是复杂度得不到保证$
$最后用dp做了这道题,dp[i][j]表示第i个数放j是否能使前i个数字合法$
$记录一下每个状态是否可达，之后从最后一位往前每个位置选一个合法的就可以了。$
代码

#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 1e5+10;
int dp[maxn][7];
int a[maxn];
int b[maxn];
vector<int> tmp;
int main()
{
    int n;scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d",&a[i]);for(int i=1;i<=5;i++) dp[1][i]=1;for(int i=2;i<=n;i++){
    if(a[i]>a[i-1]){
    for(int j=1;j<=5;j++){
    for(int k=j-1;k>=1;k--){
    if(dp[i-1][k]) dp[i][j]=1;}}}else if(a[i]<a[i-1]){
    for(int j=1;j<=5;j++){
    for(int k=j+1;k<=5;k++){
    if(dp[i-1][k]) dp[i][j]=1;}}}else{
    for(int j=1;j<=5;j++){
    for(int k=1;k<=5;k++){
    if(j!=k&&dp[i-1][k]) dp[i][j]=1;}}}}int flag=0;for(int i=1;i<=5;i++) tmp.push_back(i);for(int i=n;i>=1;i--){
    int ff=0;for(int j=0;j<tmp.size();j++){
    if(dp[i][tmp[j]]){
    ff=1;b[i]=tmp[j];break;}}if(i==1) break;tmp.clear();if(a[i-1]<a[i]){
    for(int j=1;j<b[i];j++) tmp.push_back(j);}else if(a[i-1]>a[i]){
    for(int j=b[i]+1;j<=5;j++) tmp.push_back(j);}else{
    for(int j=1;j<=5;j++){
    if(j!=b[i]) tmp.push_back(j);}}if(ff==0){
    flag=1;break;}}if(flag==1) printf("-1\n");else    for(int i=1;i<=n;i++) printf("%d ",b[i]);return 0;
}