撰写1 second
256 megabytes
standard input
standard output
Little Paul wants to learn how to play piano. He already has a melody he wants to start with. For simplicity he represented this melody as a sequence a1,a2,…,ana1,a2,…,an of key numbers: the more a number is, the closer it is to the right end of the piano keyboard.
Paul is very clever and knows that the essential thing is to properly assign fingers to notes he’s going to play. If he chooses an inconvenient fingering, he will then waste a lot of time trying to learn how to play the melody by these fingers and he will probably not succeed.
Let’s denote the fingers of hand by numbers from 11 to 55. We call a fingering any sequence b1,…,bnb1,…,bn of fingers numbers. A fingering is convenient if for all 1≤i≤n−11≤i≤n−1 the following holds:
- if ai<ai+1ai<ai+1 then bi<bi+1bi<bi+1, because otherwise Paul needs to take his hand off the keyboard to play the (i+1)(i+1)-st note;
- if ai>ai+1ai>ai+1 then bi>bi+1bi>bi+1, because of the same;
- if ai=ai+1ai=ai+1 then bi≠bi+1bi≠bi+1, because using the same finger twice in a row is dumb. Please note that there is ≠≠, not == between bibiand bi+1bi+1.
Please provide any convenient fingering or find out that there is none.
The first line contains a single integer nn (1≤n≤1051≤n≤105) denoting the number of notes.
The second line contains nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤2⋅1051≤ai≤2⋅105) denoting the positions of notes on the keyboard.
If there is no convenient fingering, print −1−1. Otherwise, print nn numbers b1,b2,…,bnb1,b2,…,bn, each from 11 to 55, denoting a convenient fingering, separated by spaces.
5 1 1 4 2 2
1 4 5 4 5
7 1 5 7 8 10 3 1
1 2 3 4 5 4 3
19 3 3 7 9 8 8 8 8 7 7 7 7 5 3 3 3 3 8 8
1 3 4 5 4 5 4 5 4 5 4 5 4 3 5 4 3 5 4
The third sample test is kinda “Non stop” song by Reflex.
题意：给一个a序列，按照
if ai
if ai=ai+1 then bi≠bi+1
的规则得出b序列，序列的数字是1~5代表手指且不分左右jio
题解：
明显是一道保存路径的简单dp
f[i][j]表示第i个数时选择的手指，用三重循环以及三个分类，f[i][j]=f[i][j]|f[i-1][k],k代表符合以上规则的b[i-1]，以此遍历所有情况，当f[i-1][k]==1时，记录路径pre[i][j]=k。
另外将第一层初始化为f[1][1~5]=1，并记得当n==1时特判输出1 或者不在循环内设置sign，而通过最后f[n][1~5]判断。
#include<algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <cstdio>
#include <vector>
#include <string>
#include <cmath>
#include <queue>
#include <stack>
#include <set>
#include <map>
using namespace std;
#define P(a,b,c) make_pair(a,make_pair(b,c))
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,a,n) for (int i=n;i>=a;i--)
#define CLR(vis) memset(vis,0,sizeof(vis))
#define MST(vis,pos) memset(vis,pos,sizeof(vis))
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef pair<int,pair<int,int> >pii;
typedef long long ll;
const ll mod = 1000000007;
const int INF = 0x3f3f3f3f;
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
const int maxn=1e5+10;
int a[maxn];
int b[maxn];
int f[maxn][10];
int pre[maxn][10];
void print(int i,int sign){
if(pre[i][sign])print(i-1,pre[i][sign]);
printf("%d ", sign);
}
int main(){
int n;
scanf("%d", &n);
rep(i,1,n)scanf("%d", &a[i]);
rep(i,1,5)f[1][i]=1;
int sign=0;
rep(i,2,n){
rep(j,1,5){
if(a[i]>a[i-1]){
rep(k,1,j-1){
f[i][j]|=f[i-1][k];
if(f[i-1][k]){
pre[i][j]=k;
if(i==n)sign=j;
}
}
}
if(a[i]<a[i-1]){
rep(k,j+1,5){
f[i][j]|=f[i-1][k];
if(f[i-1][k]){
pre[i][j]=k;
if(i==n)sign=j;
}
}
}
if(a[i]==a[i-1]){
rep(k,1,5){
if(j!=k){
f[i][j]|=f[i-1][k];
if(f[i-1][k]){
pre[i][j]=k;
if(i==n)sign=j;
}
}
}
}
}
}
if(n==1)printf("1\n");
else if(sign==0)printf("-1\n");
else {
print(n,sign);
cout<<endl;
}
return 0;
}