P1303 导弹拦截解题报告

Published on 2009 / 05 / 05

题目地址：http://www.vijos.cn/Problem_Show.asp?id=1303 ;

这道题相信大家在刚开始学动态规划时就做过，Vijos上的这道稍微修改了一下，所以不能直接提交原来的程序。题目要求再输出还需多少枚导弹，可以直接重复求最大，我就没有写成函数，直接用 goto 了。

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

代码如下（C语言）：

#include<stdio.h>
int i,j,k,n,max,count,f[10000],a[10000],temp[10000];
int main()
{
      char ch;
      do
          {
          scanf("%d",&a[n]);
          ch=getchar();
          n++;
          }while(ch!='\n');
      for(i=0;i<n;i++)
         f=1;
      for(i=n-2;i>=0;i--)
          {
          for(j=i+1;j<n;j++)
            if(a[j]<=a&&f[j]+1>f)
                f=f[j]+1;
          }
      for(i=0;i<n;i++)
          if(f>max)
              max=f;
      printf("%d,",max);
      k=max;
      for(i=0;i<n;i++)
          if(f==max)
              {;j=a;break;}
      for(;i<n;i++)
          if(f==max&&j>=a)
              {
              j=a;
              a=0;
              max--;
              }
      start:
      if(k!=n)
      {
          count++;
          for(i=0,j=0;i<n;i++)
              if(a!=0)
              {temp[j]=a;j++;}
          memset(a,0,sizeof(a));
          for(i=0;i<j;i++)
              a=temp;
          memset(f,0,sizeof(f));
          memset(temp,0,sizeof(temp));
          n=j;
          for(i=0;i<n;i++)
             f=1;
          for(i=n-2;i>=0;i--)
              {
              for(j=i+1;j<n;j++)
                if(a[j]<=a&&f[j]+1>f)
                    f=f[j]+1;
              }
          for(i=0;i<n;i++)
              if(f>max)
                  max=f;
          k=max;
          for(i=0;i<n;i++)
              if(f==max)
                  {;j=a;break;}
          for(;i<n;i++)
              if(f==max&&j>=a)
                  {
                  j=a;
                  a=0;
                  max--;
                  }
          goto start;
      }
      printf("%d",count);
      return 0;
}