HDU 4512 길 고 시리즈 - 완벽 한 대형 I

제목 의 대의: 하나의 서열 을 정 하고 이런 서열 을 풀 어서 이 서열 이 원래 의 서열 에서 상대 적 인 위치 가 변 하지 않 게 한다. a [0] 에서 a [middle] 까지 상승 하고 a [middle] 에서 a [n] 까지 하락 하 며 중간 요소 의 대칭 에 관 한 가장 긴 서열, 출력 이 가장 긴 길이 이다.
     이 문 제 는 처음에는 잘 이해 하지 못 했 는데 나중에 다른 사람의 알고리즘 을 보 았 는데 갑자기 가장 긴 공공 상승 서브 서열 이라는 것 을 알 게 되 었 다.왜 요?
     여기 서 대칭 적 인 먼저 상승 한 후에 떨 어 지 는 서열 을 풀 어야 하기 때문에 서열 을 거꾸로 놓 은 후에 원래 의 서열 과 가장 긴 공공 상승 서브 서열 을 풀 면 된다.최 장 공공 상승 서브 시퀀스 에 대해 서 는 최 장 공공 서브 시퀀스 를 바탕 으로 상승 여 부 를 판단 하면 된다.
#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

좋은 웹페이지 즐겨찾기