题意：求数列中最长最小子序列，所谓最小类似于字典序最小。
思路：最长递减子序列动态更新，令通过一个nex数组贪心更新字典序最小序列。
Code：
#include <string.h>
#include <cstdio>
using namespace std;
const int maxn = 1005;
int dp[maxn], nex[maxn], a[maxn];
int main()
{
int t, n, id;
scanf("%d", &t);
while(t--)
{
scanf("%d", &n); a[0] = 0;
memset(dp, 0, sizeof dp);
memset(nex, -1, sizeof nex);
for(int i = 1; i <= n; ++i) scanf("%d", &a[i]);
for(int i = n; i >= 0; --i) //操作至0，找到最终的最长最小上升子序列
for(int j = i+1; j <= n; ++j)
{
if(a[i] < a[j])
{
if(dp[i] < dp[j]+1 || dp[i]==dp[j]+1 && a[nex[i]] > a[j])
{
dp[i] = dp[j]+1;
nex[i] = j;
}
}
}
printf("%d ", dp[0]);
id = nex[0];
while(id != -1)
{
printf("%d ", a[id]);
id = nex[id];
}
puts("");
}
return 0;
}
继续加油~
