Codeforces 316B2 EKG

题目链接：http://codeforces.com/problemset/problem/316/B2

题意：一共有n个人，给出你的位置k，以及每一个人前面的人的编号(0代表不知道)，问你排在第几个

思路：相连的人可以构成一条链，预处理出除了自己所在链外每一条的长度以及自己位置在所在链的位置，然后通过dp，把可以接自己所在链的位置标为1就可以了

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

int a[maxn],fr[maxn],line[maxn],dp[maxn];

int main()
{
    int n,k,pos;
    while (scanf("%d%d",&n,&k)!=EOF)
    {
        memset(fr,0,sizeof(fr));
        for (int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            fr[a[i]]=i;
        }
        int num=0;
        for (int i=1;i<=n;i++)
        {
            if (a[i]==0)
            {
                int tem=1,flag=0;
                for (int j=fr[i];j!=0;j=fr[j])
                {
                    tem++;
                    if (j==k)
                    {
                        flag=1;
                        break;
                    }
                }

                if (i==k) pos=1;
                else if (flag) pos=tem;
                else line[++num]=tem;
            }
        }

       memset(dp,0,sizeof(dp));
       dp[0]=1;
       for (int i=1;i<=num;i++)
       {
           for (int j=n;j>=0;j--)
           {
               if (dp[j]) dp[j+line[i]]=1;
           }
       }
       for (int i=0;i<=n;i++)
       {
           if (dp[i]) printf("%d\n",i+pos);
       }
    }
}