Vova was walking along one of Shenzhen streets when he noticed young pear trees, growing along the pavement. Each tree had a plaque attached to it containing some number. Vova walked around all n trees and found out that the numbers on the plaques are pairwise distinct and fit the limits from 1 to n. Obviously, the trees were first planned to be planted in the given order, but at the moment they were strangely mixed: the sixth one, then the fourth one, then the third one, then the fifth one... There was an ice cream tray nearby. The ice cream seller noticed Vova staring at the pear trees with a bewildered look and told him that he saw the trees planted. The foreman entrusted two workers with the task and told them to plant the trees according to the numbers on the plaques. Then he left and the workers divided the trees between themselves and started working. As the foreman wasn't specific about the increasing or decreasing order of numbers on the plaques, each worker made his own decision without consulting the partner. Both workers planted trees moving in the same direction, from the same end of the street. Let's look at the sample. Let's assume that n = 8 and the workers divided the trees between themselves in such a way that the first one got trees number 1, 4 and 5 and the second one got trees number 2, 3, 6, 7 and 8. As a result, they got such sequence of numbers on the plaques: 8, 7, 1, 6, 4, 3, 5, 2 (the first one planted the trees in the increasing order and the second one planted the trees in the decreasing order). Vova wrote down all numbers on the plaques in the order, in which the trees were planted and wanted to determine which trees were planted by the first worker and which trees were planted by the second one. Help him to do this.
Input
The first line contains an integer n that is the number of trees (3 ≤ n ≤ 100 000). The second line contains n distinct integers between 1 and n describing the number permutation Vova wrote.
Output
Print in the first line two integers between 1 and ( n − 1) that are the number of trees the first and the second worker planted, respectively. In the second line print the numbers of the trees planted by the first worker, in the third line print the number of the trees planted by the second worker. The numbers must follow in the order, in which the worker planted these trees. If there are multiple solutions, you may print any of them. If there's no solution, print “Fail”.
Sample Input
| input | output |
|---|---|
| |
| |
| |
Source
Open Ural FU Personal Contest 2013
題意：有n個數，分别是1~n,随意排列，問能不能在這個排列中找出兩個序列，兩個序列必須是遞增或者遞減，而且不能有重複的 思路：我們分别對同遞增，同遞減，一遞增一遞減進行DP并記錄路徑，最後輸出即可
總算搞出來了，人也很累了，睡覺去了
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <math.h>
#include <algorithm>
using namespace std;
#define ls 2*i
#define rs 2*i+1
#define up(i,x,y) for(i=x;i<=y;i++)
#define down(i,x,y) for(i=x;i>=y;i--)
#define mem(a,x) memset(a,x,sizeof(a))
#define w(a) while(a)
#define LL long long
const double pi = acos(-1.0);
#define Len 100005
#define mod 1000000007
const int INF = 0x3f3f3f3f;
//0為遞增，1為遞減
struct node
{
int x,y;
} s[Len][2];//記錄路徑
int n;
int a[Len];
int dp[Len][2];//dp[i][j]，儲存的就是看在j狀态下，第i個位置所在的連續遞增或遞減序列，最前面那個比這個連續序列第一個大或者小的數
vector<int> ans[2];
void upp(int x,int y,int i,int j,int m)
{
if(dp[x][y]>m)
{
dp[x][y] = m;
s[x][y].x = i;
s[x][y].y = j;
}
}
void downn(int x,int y,int i,int j,int m)
{
if(dp[x][y]<m)
{
dp[x][y] = m;
s[x][y].x = i;
s[x][y].y = j;
}
}
//全遞增
int set1()
{
int i,j;
dp[1][0] = dp[1][1] = -1;
up(i,1,n-1)
{
dp[i+1][0]=dp[i+1][1] = INF;
up(j,0,1)
{
if(dp[i][j]<INF)
{
if(a[i-1]<a[i])//數組的下标對應dp的下标+1，也就是說i對應i+1
upp(i+1,j,i,j,dp[i][j]);
if(dp[i][j]<a[i])//如果不滿足j條件下的遞增，那麼就看能否儲存到j^1的條件下
upp(i+1,j^1,i,j,a[i-1]);
}
}
}
return dp[n][0]+dp[n][1]<INF;
}
//全遞減
int set2()
{
int i,j;
dp[1][0] = dp[1][1] = INF;
up(i,1,n-1)
{
dp[i+1][0]=dp[i+1][1] = -1;
up(j,0,1)
{
if(dp[i][j]>=0)
{
if(a[i-1]>a[i])
downn(i+1,j,i,j,dp[i][j]);
if(dp[i][j]>a[i])
downn(i+1,j^1,i,j,a[i-1]);
}
}
}
return dp[n][0]+dp[n][1]>0;
}
//一個遞增，一個遞減
int set3()
{
int i,j;
dp[1][0] = INF;
dp[1][1] = -1;
up(i,1,n-1)
{
dp[i+1][0] = -1;
dp[i+1][1] = INF;
if(dp[i][0]>0)
{
if(a[i-1]<a[i])
downn(i+1,0,i,0,dp[i][0]);
if(dp[i][0]>a[i])
upp(i+1,1,i,0,a[i-1]);
}
if(dp[i][1]<INF)
{
if(a[i-1]>a[i])
upp(i+1,1,i,1,dp[i][1]);
if(dp[i][1]<a[i])
downn(i+1,0,i,1,a[i-1]);
}
}
return dp[n][0]>0 || dp[n][1]<INF;
}
void solve(int x,int y)
{
if(x<=0) return;
ans[y].push_back(a[x-1]);
solve(s[x][y].x,s[x][y].y);
}
int main()
{
int i,j,k;
w(~scanf("%d",&n))
{
mem(s,0);
up(i,0,n-1)
scanf("%d",&a[i]);
if(set1() || set2() || set3())//三個隻要有一個符合即可
{
ans[0].clear();
ans[1].clear();
if(dp[n][0]>=1 && dp[n][0]<=n) solve(n,0);
else solve(n,1);
up(i,0,1)
{
if(ans[i].empty())//如果整個序列是遞增或者遞減，那麼取出一個來
{
ans[i].push_back(ans[i^1].back());
ans[i^1].pop_back();
}
}
printf("%d %d\n",ans[0].size(),ans[1].size());
up(i,0,1)
{
down(j,ans[i].size()-1,0)
{
printf("%d",ans[i][j]);
if(j)
printf(" ");
}
printf("\n");
}
}
else
puts("Fail");
}
return 0;
}