【51nod】1732 51nod婚姻介绍所

题目：

http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1732

真的卡输出啊

cstdio改为stdio.h就过，之前无限TLE

代码：

#include<stdio.h>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN=1e3+10;

int dp[MAXN][MAXN];
char a[MAXN];

int main()
{
    int n;
    scanf("%d",&n);
    scanf("%s", a);
    memset(dp,0,sizeof(dp));
    for(int i=n-1;i>=0;i--)
    {
        dp[i][i]=n-i;
        for(int j=i-1;j>=0;j--)
        {
            if(a[i]==a[j])
            {
                dp[i][j]=dp[i+1][j+1]+1;
            }
        }
    }
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        if(x<y) printf("%d\n",dp[y][x]);
        else
            printf("%d\n",dp[x][y]);
    }
    return 0;
}

把数组倒过来代码：

#include<stdio.h>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN=1e3+10;

int dp[MAXN][MAXN];
char a[MAXN];
char b[MAXN];

int main()
{
    int n;
    scanf("%d",&n);
    scanf("%s", a);
    for(int i=0;i<n;i++)
        b[n-1-i]=a[i];
    b[n]='\0';
    memset(dp,0,sizeof(dp));
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(b[i-1]==b[j-1])
                dp[i][j]=dp[i-1][j-1]+1;
            else
                dp[i][j]=0;
        }
    }
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        printf("%d\n",dp[n-x][n-y]);
    }
    return 0;
}