CFR 316 B2. EKG ( DP )

Problem - 316B2 - Codeforces

題意：
有 N 個人在排隊，不知道他們的順序，但知道某些人知道前面的人是誰，有些人不知道 ( 用 0 表示 )。求編號 X 的人有可能出現的所有位子。

資料規模：
The first line contains two integers n (1 ≤ n ≤ 1e3) and x (1 ≤ x ≤ n) — the number of beavers that stand in the queue and the Smart Beaver's number, correspondingly. All willing to get to the doctor are numbered from 1 to n.
The second line contains n integers a1, a2, ..., an (0 ≤ ai ≤ n) — the number of the beaver followed by the i-th beaver. If ai = 0, then the i-th beaver doesn't know who is should be in front of him. It is guaranteed that values ai are correct. That is there is no cycles in the dependencies. And any beaver is followed by at most one beaver in the queue.
TL: 500 ms
ML: 256 MB

解法：
因為保證合法，所以可以把所有人都歸類為某些隊。對於 X 不存在的所有對進行背包 DP，看看 X 所在的對前面可以有哪些不同的人數墊前。

時間 / 空間複雜度：
O( N^2 )

int N, M;
vi A;

void init(){
  cin >> N >> M; --M;
  A = vi( N );
  for( int i = 0; i < N; ++i ){
    cin >> A[ i ];
    --A[ i ];
  }
}

vi front;
vi back;
vvi dp;

int mpos = -1;
vi other_size;

void solve(){
  front = back = vi( N, -1 );
  for( int i = 0; i < N; ++i ){
    front[ i ] = A[ i ];
  }
  for( int i = 0; i < N; ++i ){
    if( front[ i ] == -1 ) continue;
    back[ front[ i ] ] = i;
  }
  for( int i = 0; i < N; ++i ){
    static vi vis( N );
    if( vis[ i ] ) continue;
    int u = i;
    while( front[ u ] != -1 ){
      u = front[ u ];
    }
    int size = 0;
    int found_m = 0;
    while( true ){
      vis[ u ] = 1;
      if( u == M ){
        found_m = 1;
        mpos = size;
      }
      ++size;
      if( back[ u ] == -1 ){
        break;
      }
      u = back[ u ];
    }
    if( found_m ) continue;
    other_size.emplace_back( size );
  }
  dp = vvi( other_size.size() + 1, vi( N ) );
  dp[ 0 ][ 0 ] = 1;
  for( int i = 0; i < other_size.size(); ++i ){
    for( int j = 0; j < N; ++j ){
      if( dp[ i ][ j ] == 0 ) continue;
      dp[ i + 1 ][ j ] |= dp[ i ][ j ];
      dp[ i + 1 ][ j + other_size[ i ] ] |= dp[ i ][ j ];
    }
  }
  for( int i = 0; i < N; ++i ){
    if( dp[ other_size.size() ][ i ] == 0 ) continue;
    cout << i + mpos + 1 << endl;
  }
}