PersonalCorpus 版 (精华区)

Your C++ program has solved Ok the problem 497
(Strategic Defense Initiative)
in 0.020 seconds with low memory spent.


void main()
{
    int i,j,k,n,best_k;
    int a[10000],to[10000],v[10000];
    char s[100];

    scanf("%d\n",&n);
    while (n>0) {
        n--; k=-1;
        while (1) {
            if (gets(s)==NULL) break;
            if (strlen(s)==0) break;
            sscanf(s,"%d",&a[++k]);
        }
        to[k]=-1; v[k]=1; best_k=k;
        for (i=k-1;i>=0;i--) {
            v[i]=1; to[i]=-1;
            for (j=i+1;j<=k;j++) if (a[i]<a[j])
                if (v[j]+1>v[i]) { v[i]=v[j]+1; to[i]=j; }
            if (v[i]>v[best_k]) best_k=i;
        }
        printf("Max hits: %d\n",v[best_k]);
        while (best_k!=-1) {
            printf("%d\n",a[best_k]);
            best_k=to[best_k];
        }
        if (n>0) printf("\n");
    }
}