출력 최장 상승 서브시퀀스 모델(DP)

8644 단어 dp
최장 상승 서열을 출력하려면, 서열의 이전 서열과 같이 새로운pre 그룹을 추가하십시오.마지막으로 그룹을 한 번 훑어보면 됩니다.
코드는 다음과 같습니다.
#include <iostream>
#include
<cstdio>
#include
<cstring>

using namespace std;

const int N = 1000;

int num[N];
int pre[N];
int dp[N];
int f[N];


int main()
{
freopen(
"data.in", "r", stdin);
int n, i, j, ans, flag;
while(~scanf("%d", &n))
{
for(i = 1; i <= n; i++)
scanf(
"%d", &num[i]);

memset(dp,
0, sizeof(dp));
memset(pre,
0, sizeof(pre));
memset(f,
0, sizeof(f));
dp[
1] = 1;
for(i = 2; i <= n; i++)
{
ans
= dp[i];
for(j = 1; j < i; j++)
{
if(num[i] > num[j] && ans < dp[j])
{
ans
= dp[j];
if(!pre[num[i]] && !f[j])
{
pre[num[i]]
= num[j]; //
f[j] = 1;
flag
= num[i];
}
}
}
dp[i]
= ans + 1;
}
ans
= 0;
i
= flag;
while(i)
{
printf(
"%d ", i);
i = pre[i];
}
for(i = 1; i <= n; i++)
if(dp[i] > ans)
ans
= dp[i];
printf(
"
%d
", ans);
}
return 0;
}

좋은 웹페이지 즐겨찾기