P1098 合唱队形解题报告

Published on 2009 / 05 / 16

类似最长不下降子序列。记录后DP一下就过了。

编译通过…
├ 测试数据 01：答案正确… 0ms
├ 测试数据 02：答案正确… 0ms
├ 测试数据 03：答案正确… 0ms
├ 测试数据 04：答案正确… 0ms
├ 测试数据 05：答案正确… 0ms
├ 测试数据 06：答案正确… 0ms
├ 测试数据 07：答案正确… 0ms
├ 测试数据 08：答案正确… 0ms
├ 测试数据 09：答案正确… 0ms
├ 测试数据 10：答案正确… 0ms
Accepted 有效得分：100 有效耗时：0ms

#include<stdio.h>
int N,people[100][4]; 
void Left(int a);
void Right(int a);
int Min(int a,int b);
int main()
    {
    scanf("%d",&N);
    memset(people,0,sizeof(people));
    int i,j;
    for(i=0;i<N;i++)
        scanf("%d",&people[0]);
    N--;
    people[0][1]=0;
    people[N][2]=0;
    for(i=1;i<=N;i++)
        Left(i);
    for(i=N-1;i>=0;i--)
        Right(i);
    for(i=1,j=people[0][1]+people[0][2];i<=N;i++)
        {
        people[3]=people[1]+people[2];
        if(j>people[3])
            j=people[3];
        }
    printf("%d",j);
    return 0;
    } 
int Min(int a,int b)
{
    if(a>b)
        a=b;
    return(a); 
}
void Left(int a)
{
     int i,j,k;
     for(i=0,j=a;i<a;i++)
         if(people[a][0]>people[0])
             {j=a-i-1+people[1];break;}
     for(i=0;i<a;i++)
         if(people[a][0]>people[0])
         {
             k=a-i-1+people[1];
             j=Min(j,k);
         }
     people[a][1]=j;
}
void Right(int a)
{
     int i,j,k;
     for(i=a+1,j=N-a;i<=N;i++)
         if(people[a][0]>people[0])
             {j=i-a-1+people[2];break;}
     for(i=a+1;i<=N;i++)
         if(people[a][0]>people[0])
         {
             k=i-a-1+people[2];
             j=Min(j,k);
         }
     people[a][2]=j;
}