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

「QQ红包」

2017-07-05 11:49:09

Solution

一道比较简单的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; } ```