回文密码

T2.回文密码（password.cpp/pas/in/out）

时间限制：1s

空间限制：256MB

伊利斯.逐星：多亏了你的相助，我们通过了第一层。那些蜘蛛真是另令人作呕。现在，我们来到了城堡二层，但是……恐怕又要麻烦你了。

布莱恩.铜须：你猜猜我们看到了什么？乌瑟尔！我的好朋友，他的尸体就这么被克尔苏加德转化成为了亡灵！还被冻在冰块里！我一定要找到这个可恶的死灵法师，把他砸成肉饼！

芬利.莫格顿：%^&##@#%^

（旁边还有克尔苏加德留给我们的谜题！上面写着……）

雷诺.杰克逊：糟了！我们必须在一秒内解开密码，否则……乌瑟尔将会从冰雕里……解放出来……将我们杀掉。

题目描述：

他们又遇到麻烦了，现在需要你帮助他们解开克尔苏加德的密码。

有这样一串数字和若干次询问，对于每次询问，求出该询问区间的最长回文子串长度，所有的结果的组合就是通往下一层的密码

数据输入：

第一行n表示数字串长度，第二行一串长度为n的数字串（数字范围0~9）。第三行m表示询问的次数，第4~4+m-1行每行一组Li，Ri表示询问区间。

数据输出：

m行，每行对应一个询问。

输入样例：

1 2 3 4 5 5 4 3 2 1

1 10

2 9

输出样例：

数据范围：

0<n<=100000,0<m<=1000000，|Ri-Li|<=20

前30%，n,m<=200;

30%~60%,n,m<=2000;

2014级学长老爷子（冯俊杰）出的题，质量还是相当高的，是一个dp，f[i][j]表示从i开始长度为j的序列中最长的回文序列的长度，转移方程为

if(f[i+1][j-2]==j-2&&a[i]==a[i+j-1])

f[i][j]=j;

else

f[i][j]=max(f[i+1][j-1],f[i][j-1]);

长度是外循环。

#include<bits/stdc++.h>
using namespace std;

int n,m;
int a[201000];
int f[201000][210];

void in(int &x)
{
    char c=getchar();x=0;
    while(c<'0'||c>'9')c=getchar();
    while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
}

void out(int x)
{
    if(x>9) out(x/10);
    putchar(x%10+'0');
}

int main()
{
    
  freopen("password.in","r",stdin);
  freopen("password.out","w",stdout);
  cin>>n;
  for(int i=1;i<=n;i++)
      in(a[i]);
  for(int i=1;i<=n;i++)
      f[i][1]=1;
      
 for(int j=2;j<=n&&j<=200;j++)
  for(int i=1;i+j-1<=n;i++)
    {
        if(f[i+1][j-2]==j-2&&a[i]==a[i+j-1])
          f[i][j]=j;
        else
          f[i][j]=max(f[i+1][j-1],f[i][j-1]);
    }
    in(m);
    int x,y;
    for(int i=1;i<=m;i++)
      {
          in(x),in(y);
          out(f[x][y-x+1]);
          putchar('\n');
      }
  return 0;
}

回文密码

推荐阅读