题解 P2743 【[USACO5.1]乐曲主题Musical Themes】

「QQ红包」 · 2017-07-05 11:49:09 · 题解

一道比较简单的dp题

f[i][j]表示以 第一个部分以第i个字符为结尾，第二个部分以第j个字符为结尾，主题的长度。

dp转移方程f[i][j]=f[i-1][j-1]+1（a[i]-a[i-1]==a[j]-a[j-1]）

              f[i][j]=1(a[i]-a[i-1]!=a[j]-a[j-1])

然而不能有重叠部分，我们可以发现，f[i][j]最大为j-i，所以要加个限制f[i-1][j-1]+1<=j-i

然后开5k*5k的数组会炸（在usaco上），所以用滚动数组（多棒）

/*
ID: ylx14271
PROG: theme 
LANG: C++     
*/
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
int a[5010];
int i,j,k,n;
int f[2][5010]; 
int ans;
int main()
{
    freopen("theme.in","r",stdin);
    freopen("theme.out","w",stdout);
    scanf("%d",&n);
    for (i=1;i<=n;i++) scanf("%d",&a[i]);//读入
    for (i=1;i<n-4;i++)//因为长度最大为5，所以只搞到n-4
        for (j=i+1;j<=n;j++)//不能重叠，所以i+1开始
        {
            if (a[i]-a[i-1]==a[j]-a[j-1]&&f[(i-1)%2][j-1]+1<=j-i)
            f[i%2][j]=f[(i-1)%2][j-1]+1; else f[i%2][j]=1;
            ans=max(ans,f[i%2][j]);
        }
    if (ans<5) ans=0;
    printf("%d\n",ans);//输出
    return 0;
}