一道比较简单的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上),所以用滚动数组(多棒)
```cpp
/*
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;
}
```