题目描述：
给定一个长度为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 取模。
题解：
方案数统计不带修改不难想到dp，
又有字符串的处理，加上信息不够，可以想到用区间 [l,r] 来存储信息的形式
所以，定义 f[i][j] 表示取 [i,j] 为最后一段的总方案数
容易想到，当 [k,i-1] 的长度小于 [i,j] 的长度时，必有 v[i,j] > v[k,i-1] (先比较位数)，f[i][j]+=f[k][i-1]
当 [k,i-1] 的长度大于 [i,j] 的长度时，必有 v[i,j] < v[k,i-1] ，f[i][j] 不能由 f[k][i-1] 转移来
当 [k,i-1] 的长度等于 [i,j] 的长度，即 k=i-1-(j-i+1)-1=2*i-j-1 时，通过比较 v[i,j]，v[k,i-1] 来判断能否由 f[k][i-1] 转移来
怎么比较呢？
字符串的比较方式 ，不难想到hash
但是hash只能处理字符串相同的情况，无法得出严格的大小关系
比较字符串大小是从靠前的位置开始的
所以可以用二分找出第一位不同的，比较字符即可
最后考虑到要处理 f[k][i-1] 的总和 (2*i-j<=k<=i-1)，将 f[][] 维护成前缀和
因此答案刚好是 f[n][n]
注意： ch[i]==‘0‘ 时方案数为0
#include<bits/stdc++.h> using namespace std; typedef long long ll; const ll mod=1000000007; const int N=5005; int n; ll v[N][N],f[N][N]; char ch[N]; bool check(int a,int b,int c,int d){ if(v[a][b]==v[c][d])return 0; int l=0,r=b-a,mid; while(l<r){ mid=(l+r)>>1; if(v[a][a+mid]!=v[c][c+mid])r=mid; else l=mid+1; } if(ch[a+l]<ch[c+l])return 1; return 0; } int main(){ scanf("%d",&n); scanf("%s",ch+1); for(int i=1;i<=n;i++) for(int j=i;j<=n;j++) v[i][j]=(v[i][j-1]*10+ch[j]-‘0‘)%mod; for(int j=1;j<=n;j++) f[1][j]=1; for(int i=2;i<=n;++i){ for(int j=i;j<=n;++j){ if(ch[i]==‘0‘) f[i][j]=0; else{ int r=i-1,l=i+i-j-1; f[i][j]=((f[r][r]-f[max(0,l)][r])%mod+mod)%mod; if(l>0&&check(l,r,i,j)){ f[i][j]=(f[i][j]+((f[l][r]-f[l-1][r])%mod+mod)%mod)%mod; } } f[i][j]=(f[i][j]+f[i-1][j])%mod; } } printf("%lld\n",f[n][n]); return 0; }
原文：https://www.cnblogs.com/HarryPotter-fan/p/11396901.html