2124: 信息学奥赛一本通T1259-求最长不下降序列（DP）指定输出顺序

解题思路:DP, 以i节点为结束的最长不下降序列 f[i] = max(f[i], f[j] + 1)  j > 1 && j < i;

注意事项:输出顺序小数优先：判断相等最长情况下， 采用小数优先 else if(f[i] == f[j] + 1 && a[j] < a[g[i]]){

参考代码:

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 2e2 + 10;
int f[N],a[N],g[N],ans[N]; 
int main()
{
	int n;
	cin >> n;
	for(int i = 1; i <= n; i ++) cin >> a[i];
	for(int i = 1; i <= n; i ++)
	{
		f[i] = 1; 
		for(int j = 1; j < i; j ++){
			if(a[i] >= a[j])
				if(f[i] < f[j] + 1){
					f[i] = f[j] + 1;
					g[i] = j;
				}
				else if(f[i] == f[j] + 1 && a[j] < a[g[i]]){
					g[i] = j;
				}				
		}
	}
	int k = 1;
	for(int i = 1; i <= n; i ++) if (f[k] < f[i]) k = i;
	int len = f[k];
	cout <<"max="<< f[k] << endl;
	for(int i = 0; i < len; i ++){
		ans[i] = a[k];
		k = g[k];
	}
	for(int i = len - 1; i >= 0; i --) 
		cout << ans[i] << ' ';
	return 0;
}