HDU - 4745 Two Rabbits

1186 단어
제목: 길이가 n인 고리 모양의 서열을 제시한다. 두 토끼는 각각 한 점에서 출발한다. 하나는 시계 반대 방향으로 뛰고, 하나는 시계 반대 방향으로 뛴다. 매 순간 두 토끼가 있는 숫자가 똑같아야 한다. 토끼는 최대 한 바퀴를 뛴다. 토끼들은 최대 몇 번을 뛸 수 있느냐고 묻는다.
사고방식: 가장 긴 답장열을 구한 다음에 dp[0,i]+dp[i+1, n-1]를 매거하면 최대치이다. 토끼 한 마리가 [0,i]에서 대칭적인 점부터 시작하고 다른 한 마리가 [i+1, n-1]의 대칭점부터 뛴다. 두 마리 토끼가 모두 얼마나 뛰었는지 주의해서 구한다.
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 1005;

int dp[MAXN][MAXN],a[MAXN];
int n;

int main(){
    while (scanf("%d",&n) != EOF && n){
        memset(dp,0,sizeof(dp));
        for (int i = 0; i < n; i++)
            scanf("%d",&a[i]);
        for (int i = 0; i < n; i++)
            dp[i][i] = 1;
        for (int i = n-1; i >= 0; i--)
            for (int j = i+1; j < n; j++)
                if (a[i] == a[j])
                    dp[i][j] = dp[i+1][j-1] + 2;
                else dp[i][j] = max(dp[i][j-1],dp[i+1][j]);
        int ans = 1;
        for (int i = 0; i < n; i++)
            ans = max(ans,dp[0][i]+dp[i+1][n-1]);
        printf("%d
",ans);
    }    
    return 0;
}
XSL 시작 2 스타일시트에 지정된 형식
VueJS에서 ion-nav를 사용하여 Ionic Modals에서 탐색하는 방법

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage