文章

20

粉丝

412

获赞

11

访问

155.0k

头像
动态规划:最长递减子序列
P1836 山东大学机试
发布于2021年4月26日 10:18
阅读数 7.6k

#include <iostream>
#include <string.h>
using namespace std;

int main() {
	int n, m, maxlen = 1;
	int a[105], b[105], dp[105];
	
	cin >> n;
	for(int i = 1;i <= n;i++) {
		cin >> a[i];
		dp[i] = 1;
	}
	
	for(int i = 1;i <= n;i++) {
		for(int j = i;j > 0;j--)
			if(a[j] > a[i]) {
				dp[i] = max(dp[j]+1, dp[i]);
			}
		maxlen = max(maxlen, dp[i]);
	}
	
	m = maxlen;
	memset(b, 0, sizeof(b));
	for(int i = n;i > 0;i--) {
		if(dp[i] == m)
			b[m--] = a[i];
		for(int j = i+1;j <= n;j++) {
			if(dp[i] == dp[j] && a[i] > b[dp[i]+1])
				b[dp[i]] = a[i];
		}
	}
	
	for(int i = 1;i <= maxlen;i++)
		cout << b[i] << " ";
	cout << endl;
	return 0;
}

 

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发