(Description)
【题目描述】
给定一个长度为(n)的由(['0'..'9'])组成的字符串(s)，(v[i,j])表示由字符串(s)第(i)到第(j)位组成的十进制数字。
将它的某一个上升序列定义为：将这个字符串切割成(m)段不含前导('0')的串，切点分别为(k_{1},k_{2}...k_{m-1})，使得(v[1,k_{1}]<v[k_{1}+1,k_{2}]<...<v[k_{m-2}+1,k_{m-1}])。
请你求出该字符串(s)的上升序列个数，答案对(10^9+7)取模。
(Input)
第一行一个整数(n),表示字符串长度；
第二行(n)个(['0'..'9'])内的字符，表示给出的字符串(s)。
(Output)
仅一行表示给出字符串(s)的上升序列个数对(10^9+7)取模的值。
(SampleInput1)
6
123434
(SampleOutput1)
8
(SampleInput2)
8
20152016
(SampleOutput2)
4
(Hint)
对于(30\%)的数据满足：(n<=10)；
对于(100\%)的数据满足：(n<=5000)。
思路
看到这道题，特征十分明显：求方案数，数值较大（要mod），所以我们果断选择(dp)
我们设数组(dp[i][j])表示第一段以(i)开头，长度为(jsim (n-i+1))的方案数的和
于是，我们最后的答案为(dp[1][1])，表示第一段以(1)开头，长度为(1sim n)的方案数的和
接着，我们设(a[i][j])表示(s[i][n])（以下(s)就表示字符串）与(s[j][n])的最长公共前缀
显而易见，我们得到(s[i][i+a[i][j]-1]=s[j][j+a[i][j]-1])
则我们在推状转方程时会有三种情况
(1.) (dp[i][n-i+1]=1)，显而易见，这种情况下这一段直接到(n)，所以值为(1)
(2.) 我们来比较一下两个相邻且长度相等为(j)的字符串所组成的十进制数(s[i][i+j-1])与(s[i+j][i+2 imes j-1])的大小
(2.1) 若(s[i][i+j-1]<s[i+j][i+2 imes j-1])，那么满足要求，则有
dp[i][j]=dp[i+j][j]
(2.2) 若(s[i][i+j-1]ge s[i+j][i+2 imes j-1])，因为两个字符串长度相等，若后者再往后多一位，还是比前者大，于是有
dp[i][j]=dp[i+j][j+1]
最后，因为要满足(dp[i][j])的定义，我们还要将(dp[i][j])加上(dp[i][j+1])，至于为什么，自行理解
现在，推完了状转方程，我们回过头来考虑怎么比较两个数的大小
我们可以比较(s[i][i+a[i][i+j]])与(s[i+j][i+j+a[i][i+j]])的大小，既可以比较两个数大小
但是我们考虑一种情况，若(i+a[i][i+j]>i+j-1)，那么事情就一发不可收拾了，于是我们要取(min(j-1,a[i][j]))。
代码：
#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int n;
char s[5010];
int a[5010][5010];
int dp[5010][5010];
bool check(int i,int j)
{
int len=min(j-1,a[i][i+j]);
return s[i+len]<s[i+j+len];
}
int main()
{
scanf("%d %s",&n,s+1);
for(int i=n;i>0;i--)
{
for(int j=i+1;j<=n;j++)
{
if(s[i]==s[j])a[i][j]=a[i+1][j+1]+1;
}
}
for(int i=n;i>0;i--)
{
if(s[i]!='0')
{
dp[i][n-i+1]=1;
for(int j=1;j<=n-i;j++)
{
if(check(i,j))dp[i][j]=dp[i+j][j];
else dp[i][j]=dp[i+j][j+1];
}
for(int j=n-i;j>0;j--)dp[i][j]=(dp[i][j]+dp[i][j+1])%mod;
}
}
printf("%d
",dp[1][1]);
}