admin管理员组文章数量:1550649
题目大意:同标题。
解题策略:输入要注意,降序输出LIS可以用一个简单的递归搞定,升序花了点功夫。
/*
UVA 497 Strategic Defense Initiative
AC by J.Dark
ON 2013/4/1
Time 0.012s
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;
const int maxn = 10000;
int num[maxn], length[maxn], mark[maxn], numCount;
void Solve(){
for(int i=1; i<=numCount; i++) length[i] = 1;
for(int i=1; i<=numCount; i++) mark[i] = -1;
//找出最大长度及序列
for(int i=1; i<=numCount; i++){
for(int j=1; j<i; j++){
if(num[j] < num[i]){ //找出num[i]可跟在哪些数字之后
if(length[j]+1 > length[i]){
length[i] = length[j]+1;
mark[i] = j; //num[i]接在num[j]之后
}
}
}
}
int maxAns = 0, maxPos;
//找出上升序列最大长度 最大上升序列最末元素位置
for(int i=1; i<=numCount; i++){
if(maxAns < length[i]){
maxAns = length[i];
maxPos = i;
}
}
int LIS[maxn], k = maxPos;
for(int i=maxAns; i>0; i--){ //记录LIS
LIS[i] = num[k];
k = mark[k];
}
printf("Max hits: %d\n", maxAns);
for(int i=1; i<=maxAns; i++) cout << LIS[i] << endl;
}
///
int main(){
int testCase;
char temp[50];
while(cin >> testCase)
{
getchar(); //万恶的输入,浪费时间……
getchar();
for(int i=0; i<testCase; i++){
numCount = 0;
while(gets(temp) && strlen(temp))
{
num[++numCount] = atoi(temp); //表示atoi函数让我感觉之前动不动字符流的方法土爆了……
}
if(i > 0) cout << endl;
Solve();
}
}
//system("pause");
return 0;
}
版权声明:本文标题:UVA 497 Strategic Defense Initiative【最长严格递增子序列长度及打印】 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://m.elefans.com/xitong/1727253652a1105132.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论