HDU 4512 길 고 시리즈 - 완벽 한 대형 I
1335 단어 2013 년 텐 센트 프로 그래 밍 마라톤
이 문 제 는 처음에는 잘 이해 하지 못 했 는데 나중에 다른 사람의 알고리즘 을 보 았 는데 갑자기 가장 긴 공공 상승 서브 서열 이라는 것 을 알 게 되 었 다.왜 요?
여기 서 대칭 적 인 먼저 상승 한 후에 떨 어 지 는 서열 을 풀 어야 하기 때문에 서열 을 거꾸로 놓 은 후에 원래 의 서열 과 가장 긴 공공 상승 서브 서열 을 풀 면 된다.최 장 공공 상승 서브 시퀀스 에 대해 서 는 최 장 공공 서브 시퀀스 를 바탕 으로 상승 여 부 를 판단 하면 된다.
#include
#include
#include
#include
#include
#define maxn 206
#define max(a,b) a>b?a:b
using namespace std;
int a[maxn];
int dp[maxn]; //dp[i] i
int main()
{
int Tcas;
scanf("%d",&Tcas);
while(Tcas--)
{
int n;
scanf("%d",&n);
for(int i=0;i=0;i--)
{
int len = 0;
for(int j=0;j<=i;j++)
{
if(a[j] < a[i])
len = max(len,dp[j]);
else if(a[j]==a[i])
dp[j] = len + 1;
if(j