UESTC--1267

原题链接：http://www.acm.uestc.edu.cn/problem.php?pid=1267

分析：此题麻烦之处在于要输出最小最长上升子序列，关键在于如何解决最小这个问题.

我的做法是从最后一个数开始往前扫描，同时另开一重循环，从该数num[i]前一个往前扫描，即j=i-1~0.

如果num[j]<num[i]，则分三种情况：

　　 (该过程中维护一个nxt数组，表示在所求序列中的与一个数相邻的下一个数)

1.如果num[j]<num[i],但nxt[j]没有任何指向，更新 nxt[j]=i;

2.如果num[j]<num[i],并且nxt[j]指向i会使序列长度增加，则更新nxt[j]=i;

3.如果num[j]<num[i],并且nxt[j]指向i会使序列的大小减小，则更新nxt[j]=i.

 1 #include<cstdio>
 2 using namespace std;
 3 int num[1005];
 4 int dp[1005];
 5 int nxt[1005];
 6 int main()
 7 {
 8     int T;
 9     scanf("%d",&T);
10     while(T--)
11     {
12         int n;
13         scanf("%d",&n);
14         for(int i=0;i<n;i++)
15         scanf("%d",&num[i]);
16         for(int i=0;i<n;i++)
17         {
18             dp[i]=1;nxt[i]=-1;
19         }
20         for(int i=n-1;i>0;i--)
21         for(int j=i-1;j>=0;j--)
22         {
23             if(num[j]<num[i])
24             {
25                 if(nxt[j]==-1)
26                 {
27                     nxt[j]=i;
28                     dp[j]=dp[i]+1;
29                 }
30                 else if(dp[j]<dp[i]+1)
31                 {
32                     dp[j]=dp[i]+1;
33                     nxt[j]=i;
34                 }
35                 else if(dp[j]==dp[i]+1&&num[nxt[j]]>num[i])nxt[j]=i;
36             }
37         }
38         int ans=0,pos=0;
39         for(int i=0;i<n;i++)
40         if(dp[i]>ans)
41         {
42             ans=dp[i];pos=i;
43         }
44         else if(dp[i]==ans&&num[i]<num[pos])pos=i;
45         printf("%d ",ans);
46         for(int i=pos;i!=-1;i=nxt[i])
47         printf("%d ",num[i]);
48         printf("
");
49     }
50     return 0;
51 }

View Code