NKOJ 2522 Sandy的卡片（差分数组+DP）

发表于 |
字数统计: 878字 | 阅读时长 ≈ 4min

P2522【SDOI2008】Sandy的卡片

问题描述

Sandy和Sue的热衷于收集干脆面中的卡片。
然而，Sue收集卡片是因为卡片上漂亮的人物形象，而Sandy则是为了积攒卡片兑换超炫的人物模型。
每一张卡片都由一些数字进行标记，第i张卡片的序列长度为Mi，要想兑换人物模型，首先必须要集够N张卡片，对于这N张卡片，如果他们都有一个相同的子串长度为k，则可以兑换一个等级为k的人物模型。相同的定义为：两个子串长度相同且一个串的全部元素加上一个数就会变成另一个串。
Sandy的卡片数远远小于要求的N，于是Sue决定在Sandy的生日将自己的卡片送给Sandy，在Sue的帮助下，Sandy终于集够了N张卡片，但是，Sandy并不清楚他可以兑换到哪个等级的人物模型，现在，请你帮助Sandy和Sue，看看他们最高能够得到哪个等级的人物模型。

输入格式

第一行为一个数N，表示可以兑换人物模型最少需要的卡片数，即Sandy现在有的卡片数
第i+1行到第i+N行每行第一个数为第i张卡片序列的长度Mi，之后j+1到j+1+Mi个数，用空格分隔，分别表示序列中的第j个数

输出格式

一个数k，表示可以获得的最高等级。

样例输入

2
2 1 2
3 4 5 9

样例输出

2

提示

30%的数据保证n<=50
100%的数据保证n<=1000,m<=200

首先需要明白题目中全部加上一个数，意思是将一个区间整体加上一个数。
那么显然用差分，差分一下之后就变成了求这n个串的最长公共子串。

这里只记录一种比较好理解的DP方法。
令$G[i]$表示将每个串与1号串匹配后，以1号串第i个字符作为结尾的子串的最长公共串的长度。
然后将每个串和1号串直接跑一次最长公共子串，$F[i][j]$表示第$k$个串和第1个串匹配的结果。
那么令$Q[i]=max(F[i][j])，j取1-m$
那么$Q[i]$就表示了第$k$个串和第1个串匹配时，以1号串第$i$个字符作为结尾的最长公共子串长度。
然后用$Q[i]$更新$G[i]$，即$G[i]=min(G[i],Q[i])$。
所有串都讨论完了之后，取$max(G[i])$就是答案。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#define N 1005
#define M 205
using namespace std;
int n,A[N][M],F[M][M],G[M],Q[M],ans;
int main()
{
	int i,j,k,x,y;
	scanf("%d",&n);
	for(i=1;i<=n;i++)
	{
		scanf("%d%d",&A[i][0],&x);
		for(j=1;j<A[i][0];j++)
		{
			scanf("%d",&y);
			A[i][j]=y-x;x=y;
		}
	}
	for(i=1;i<A[1][0];i++)G[i]=i;
	for(i=2;i<=n;i++)
	{
		memset(Q,0,sizeof(Q));
		for(j=1;j<A[1][0];j++)
		for(k=1;k<A[i][0];k++)
		{
			if(A[i][k]==A[1][j])F[j][k]=F[j-1][k-1]+1;
			else F[j][k]=0;
			Q[j]=max(Q[j],F[j][k]);
		}
		for(j=1;j<A[1][0];j++)G[j]=min(G[j],Q[j]);
	}
	for(i=1;i<A[1][0];i++)ans=max(ans,G[i]);
	cout<<ans+1;
}