1201.cpp

ZOJ 动态规划算法题目入门与提高 源代码

#include<cstdio>
#include<string.h>

int P[51];
int I[51];

int main()
{
    //freopen("in.txt","r",stdin);
    int n,temp;
    char c;
    while(scanf("%d\n",&n)!=EOF&&n)
    {
        scanf("%c",&c);
        if(c=='P')
        {
            for(int i=1;i<=n;i++)
            {
                scanf("%d",&temp);
                P[i]=temp;
                int total=0;
                for(int j=1;j<i;j++)
                {
                    if(P[j]>P[i]) total++;
                }
                I[temp]=total;
            }
            for(int i=1;i<=n-1;i++)
                printf("%d ",I[i]);
            printf("%d\n",I[n]);
        }
        else if(c=='I')
        {
            memset(P,0,sizeof(P));
            for(int i=1;i<=n;i++)
            {
                scanf("%d",&temp);
                int t=0,j;
                for(j=1;j<=n;j++)
                {
                    if(P[j]==0) t++;
                    if(t==temp+1) break;                    
                }
                P[j]=i;
            }
            for(int i=1;i<=n-1;i++)
               printf("%d ",P[i]);
            printf("%d\n",P[n]);
        }
    }

}