USACO theme

이 문제는 길이가 5000을 넘지 않는 열을 주고 주제열을 구해 보라는 뜻이다. 그 중에서 주제열의 정의는 이 열에서 두 번 중복되어 중첩된 부분이 없고 두 열이 각각 한 수를 줄인 후 서열이 같다는 것이다.우리는 dp[i][j]를 i위치와 j위치에서 같은 직렬의 길이로 정의할 수 있다. dp[i][j]=dp[i+1][j+1]+1;그 중에서num[j+1]-num[i+1]=num[j]-num[i]는 이 답을 구한 후에 중첩 여부를 판단하고 마지막 답안도 1을 추가해야 한다. 코드는 다음과 같다.

/*
    ID: m1500293
    LANG: C++
    PROG: theme
*/

#include <cstdio>
#include <cstring>
#include <algorithm>


using namespace std;
int num[5000+10];
short dp[2][5010];   //dp[i][j] i, j         

int main()
{
    freopen("theme.in", "r", stdin);
    freopen("theme.out", "w", stdout);
    int N;
    scanf("%d", &N);
    for(int i=1; i<=N; i++) scanf("%d", &num[i]);
    short res = 0;
    for(int i=N; i>=1; i--)
    {   memset(dp[i%2], 0, sizeof(dp[1]));
        for(int j=N; j>=1; j--)
        {

            if(j+1<=N && i+1<=N && num[j+1]-num[i+1]==num[j]-num[i]) dp[i%2][j] = dp[(i+1)%2][j+1] + 1;
            else dp[i%2][j] = 0;
            int x=j, y=j+dp[i%2][j]-1+1;
            if(!((i>=x&&i<=y)||(i+dp[i%2][j]-1+1>=x&&i+dp[i%2][j]-1+1<=y)))
                res = max(res, dp[i%2][j]);
        }
        //printf("
");
    }

    if(res+1>=5) printf("%d
", res+1);
    else printf("0
");
    return 0;
}