#include <stdio.h>
#include <string.h>
char time[20];
char phone[20];
struct Call
{
   int m;
   int d;
   int h;
   int s;
   int sign;
}arr[1010];
int dp[1010];
int cmp(int i,int j)
{
   if(arr[i].m<arr[j].m) return -1;
   if(arr[i].m>arr[j].m) return 1;
   if(arr[i].d<arr[j].d) return -1;
   if(arr[i].d>arr[j].d) return 1;
   if(arr[i].h<arr[j].h) return -1;
   if(arr[i].h>arr[j].h) return 1;
   if(arr[i].s<arr[j].s) return -1;
   if(arr[i].s>arr[j].s) return 1;
   return 0;
}
int main()
{
   int n,t,p,f,i,j,k,min;
   char chr;
   while(scanf("%d",&n)&&n)
   {
      for(i=1;i<=n;i++)
      {
         scanf("%s %s %c",time,phone,&chr);
         sscanf(time,"%d:%d:%d:%d",&arr[i].m,&arr[i].d,&arr[i].h,&arr[i].s);
         if(chr=='+') arr[i].sign=1;
         else arr[i].sign=0; 
      }
      arr[0].m=arr[0].d=arr[0].m=arr[0].s=-1;
      arr[0].sign=0;
      memset(dp,-1,sizeof(dp));
      dp[0]=0;
      for(i=1;i<=n;i++)
      {
         f=0;
         for(j=i-1;j>=0;j--) 
         {
            t=cmp(j+1,j);
            if(t==0||t==-1) break;
            if(dp[i]==-1||dp[j]+1<dp[i]) dp[i]=dp[j]+1;
            if(arr[j].sign==1)
            {
               f=1;
               break;
            }
         }
         for(k=j;k>=0&&!f;k--)
         {
            t=cmp(i,k);
            p=cmp(k,k+1);
            if(t==1||(k!=j&&p!=-1)) break;
            if(dp[i]==-1||dp[k]+1<dp[i]) dp[i]=dp[k]+1;
            if(arr[k].sign==1) break;
         }
      }
      min=dp[n];
      for(i=n-1;i>=1&&arr[n].sign==0;i--)
      {
         t=cmp(i+1,i);
         if(t==0||t==-1) break;
         if(dp[i]<min) min=dp[i];
         if(arr[i].sign==1) break;
      }
      printf("%d\n",min);
   }
   return 0;
}

• 能帮我看一下这组数据应该输出什么吗？我是不是看错题了． (180) nuanran 2006-08-08 10:11:30
  • 晕，原来前面那些负的就不用保存了，还以为dp有问题，WA死了，还是没有很好的理解题意 (191) nuanran 2006-08-08 10:18:25