【XSY2564】sequence

Description

【题目描述】

给定一个长度为n的由['0'..'9']组成的字符串s，v[i,j]表示由字符串s第i到第j位组成的十进制数字。

将它的某一个上升序列定义为：将这个字符串切割成m段不含前导'0'的串，切点分别为k1,k2...km-1，使得v[1,k1]<v[k1+1,k2]<...<v[km-2,km-1]。

请你求出该字符串s的上升序列个数，答案对 10^9+7 取模。

【输入数据】

第一行一个整数n,表示字符串长度；

第二行n个['0'..'9']内的字符，表示给出的字符串s。

【输出数据】

仅一行表示给出字符串s的上升序列个数对10^9+7取模的值。

【样例输入1】

6

123434

【样例输出1】

【样例输入2】

8

20152016

【样例输出2】

【数据范围】

对于30%的数据满足：n<=10；

对于100%的数据满足：n<=5000。

考虑DP

因为保证$v[i][j]!=0$

所以设$dp[i][j]$表示将以i为起始往后移动j个字符（i也算）为结束所产生的上升序列个数。

我们用后缀和，这样答案就是$dp[1][1]$。

用a数组记录从两个点开始最多重复多少个字符，以便于我们比较大小。

如果以i开始的字符串比以i+j开始的字符串小，符合题意,更新。

$dp[i][j]+=dp[i+j][j]$

如果以i开始的字符串大于等于以i+j开始的字符串，只能由这一位后面的全部字符更新。

$ dp[i][j]+=dp[i+j][j+1]$

综上。

#include<bits/stdc++.h>

#define mod 1000000007

using namespace std;

int a[5010][5010],dp[5010][5010],n;

char ch[5010];

bool check(int x,int y)

{

    int l=min(y-x-1,a[x][y]);

    return ch[x+l]<ch[y+l];

}

int main()

{

    scanf("%d%s",&n,ch+1);

    for(int i=n;i;i--)

    {

        for(int j=i+1;j<=n;j++)

        {

            if(ch[i]==ch[j])

            {

                a[i][j]=a[i+1][j+1]+1;

            }

        }

    }

    for(int i=n;i;i--)

    {

        if(ch[i]=='0')

        {

            continue;

        }

        dp[i][n-i+1]=1;

        for(int j=1;j<=n-i;j++)

        {

            if(check(i,i+j))

            {

                dp[i][j]=(dp[i][j]+dp[i+j][j])%mod;

            }else{

                dp[i][j]=(dp[i][j]+dp[i+j][j+1])%mod;

            }

        }

        for(int j=n-i;j;j--)

        {

            dp[i][j]=(dp[i][j]+dp[i][j+1])%mod;

        }

    }

    printf("%d\n",dp[1][1]%mod);

    return 0;

}

巴特西

【XSY2564】sequence

最新文章

热门文章