首页 > ACM题库 > HDU-杭电 > HDU 3525-Orienteering[解题报告]HOJ
2014
11-05

HDU 3525-Orienteering[解题报告]HOJ

Orienteering

问题描述 :

The Orienteering competition is coming soon!Now there are N players to participate in,each has his own cheering squad (lala dui) ,In order to ensure order and security competition,Each player’s cheering squad can only send 2*M beautiful mm ,M mm from North Campus,M mm from South Campus(as known that HNU consists of South Campus and North Campus)。
In order to facilitate management , the mm from the same Campus must stay at the same side of the road which means there are two Sequences and each Sequence has equal number of mm .The day of the race,each side has many positions starting from the finishing line toward the starting line numbered for the 1,2,3. . . . up to 2*n*m positions,every mm has her own favorite position,however, when she finds her favorite position is occupied by other students, she has to go to the next position, until she finds a empty position(the cost time of this process is negligible)。
For example, there is a mm whose favorite position is 3,when she goes to the position 3,there has a people over there,so she goes to the next position 4,however ,still has a people there ,until she gets the position 6 where no one occupies this position at present,so she`s position is 6,when all the people find their positions ,the teacher for the competition comes ,he finds that there are still some empty positions ,then he orders that all people move closer to the finishing line which can not change the relative positions of each mm at the both side,so finally their positon number is from 1 to n*m,now we get two sequence A,B A[i] means the mm on the ith position of this side support the player A[i],B[i] means the mm on the ith position of the opposite side support the player B[i].
Now the teacher has Picking a speaker , the mm supporting different players must wear different clothes, but those who support the same player should wear the same clothes. In order to make the venue more harmonious visual effect,to choose two sequence (A[c[1]],A[c[2]],……A[c[len]]) (B[d[1]],B[d[2]],…..B[d[len]]),A[c[i]]=B[d[i]] (1=i<=len) The teacher want to know the max len,can you help us?Namely, you should find the max len such that there exists two identical subsequence with len elements in A and B respectively(these two subsequence need not to be continuous).

输入:

The first line of input should give the number of cases, T (at most 20).the first line of each case has two numbers n,m(1<=n<=10000,1<=m<=10)n represent the number of players,numbers from 1 to n ,m represent the number of mm of each player`s cheering squad,The next two lines,each with n*m*2 numbers,the i*2-1 number means the ith mm`s supported player number v[i](1<=v[i]<=n),the i*2 number means the ith mm`s faviourite positionw[i](1<=w[i]<=m*n), we set the mm number i is earlier than the mm number j when (i<j).

输出:

The first line of input should give the number of cases, T (at most 20).the first line of each case has two numbers n,m(1<=n<=10000,1<=m<=10)n represent the number of players,numbers from 1 to n ,m represent the number of mm of each player`s cheering squad,The next two lines,each with n*m*2 numbers,the i*2-1 number means the ith mm`s supported player number v[i](1<=v[i]<=n),the i*2 number means the ith mm`s faviourite positionw[i](1<=w[i]<=m*n), we set the mm number i is earlier than the mm number j when (i<j).

样例输入:

1
3 2
1 3 1 4 3 2 2 5 2 2 3 1
3 1 1 4 2 2 3 1 2 4 1 3

样例输出:

Case #1: 4

Hint
After the operation the A sequence is: 3 3 1 1 2 2 While The B sequence is : 3 2 3 1 2 1 The most longest common sequence is 3 3 1 1 so the len is 4.

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define maxn 200007
using namespace std;

int n, m, place[200100], next[200100], que[10100][11], data[210000];

void init(){
    memset(data,0,sizeof(data));
    memset(place,0,sizeof(place));
    for (int i=1;i<=n*m*2;i++) next[i] = i;
}

int to(int k){
    if (next[k]==k) return k;
    next[k] = to(next[k]);
    return next[k];
}

void insert_(int pos,int v){
    int a = to(pos);
    next[a] = next[a+1];
    place[a] = v;
}

void init1()
{
    int p=1;
    for (int i=1;i<=n*m*2;i++)
        if (place[i]){
            //cout<<place[i]<<endl;
            que[place[i]][0]++;
            que[place[i]][que[place[i]][0]] = p;
            p++;
        }
}

void in_(int k,int v){
    for (int i=k;i<=maxn;i+=i&(-i))
        data[i] = max(data[i],v);
}

int find_(int k){
    int ans = 0;
    for (int i=k;i>0;i-=i&(-i))
        ans = max(ans,data[i]);
    return ans;
}

int main()
{
    int T,a ,pos;
    scanf("%d",&T);
    for (int T1=1;T1<=T;T1++){
        scanf("%d %d",&n,&m);
        memset(que,0,sizeof(que));
        init();
        for (int i=0;i<n*m;i++){
            scanf("%d %d",&a,&pos);
            insert_(pos,a);
        }
        init1();
        init();
    for (int i=0;i<n*m;i++){
            scanf("%d %d",&a,&pos);
            insert_(pos,a);
    }
    for (int i=1;i<=n*m*2;i++)
        if (place[i]){
            int u = place[i];
            for (int j=que[u][0];j>0;j--){
                int v = que[u][j];
                int l = find_(v);
                in_(v+1,l+1);
            }
        }
    printf("Case #%d: %d\n",T1,find_(maxn));
    }
}

  1. a是根先忽略掉,递归子树。剩下前缀bejkcfghid和后缀jkebfghicd,分拆的原则的是每个子树前缀和后缀的节点个数是一样的,根节点出现在前缀的第一个,后缀的最后一个。根节点b出现后缀的第四个位置,则第一部分为四个节点,前缀bejk,后缀jkeb,剩下的c出现在后缀的倒数第2个,就划分为cfghi和 fghic,第3部分就为c、c

  2. 5.1处,反了;“上一个操作符的优先级比操作符ch的优先级大,或栈是空的就入栈。”如代码所述,应为“上一个操作符的优先级比操作符ch的优先级小,或栈是空的就入栈。”