题面
给定一个长度为$n$的由$[′0′..′9′]$成的字符串s$，v[i,j]$表示由字符串$s$第i到第$j$位组成的十进制数字。
将它的某一个上升序列定义为：将这个字符串切割成m段不含前导′0′的串，切点分别为$k_1,k_2…k_{m−1}$，使得$v[1,k1]<v[k_1+1,k_2]<…<v[k_{m−2},k_{m−1}]$。
请你求出该字符串s的上升序列个数，答案对$10^9+7$取模。
输入
第一行一个整数$n$,表示字符串长度；
第二行$n$个$[′0′..′9′]$内的字符，表示给出的字符串$s$。
输出
仅一行表示给出字符串$s$的上升序列个数对$10^9+7$取模的值。
样例
输入1
6
123434
输出1
8
输入2
8
20152016
输出2
4
解答
一道非常好的题
做法1.$30 ptr$
dfs爆搜，枚举每一个断点，剪剪枝，就过了，其实不剪枝也可以，因为$10!$不是特别大
做法2.$100ptr$
dp我一开始看到这道题的时候想到了加乘号那道题，用$sum[i][i]$数组表示$s[i…j]$构成的一些数，然后设计出如下方程式 \(dp[i][k] = \sum dp[i-k][len]\) 表示i结尾，最后一个数长度为k的方案数，其中保证i-k结尾长度为len的数大小小于i结尾，长度为k的数，复杂度$O(n^3)$ 但是这个思路是对的，我们考虑如何优化到n=5000的情况。用$dp[i][j]$表示i到j这个数为结尾的数的可能性的和(其实代码表示的是当且所有合法状态的和，为什么呢？因为这样可以用前缀和优化转移)。 那么dp[i][j]可以由哪些状态转移过来呢？首先如果前面一个数长度小于这个数，那么肯定可以转移，因为长度短，大小一定小。也就是说[i-1-(j-i+1)+1,i-1]都可以转过来，并且也不会去改变它的值，这里就可用前缀和优化，后面在细说。那么对于i-1-(j-i+1)+1可不可以转移过来呢？我们就要比大小了，怎么比？考虑一位一K=位地来(就向我写的DBigNumbers一样)，复杂度$O(n)$，但是这样有点爆炸啊，复杂度$O(n^3)$,5000的范围就是870 0K也帮不了我，但是考虑改了事时限，改成了2s，我们考虑套个log是可以的。那从哪里优化log呢？首先，遍历状态是不可的，那么只能是比大小的时候优化！怎么优化呢？是个技巧.我们做个哈希，然后二分对于两个数[a,b][c,d]如果前半部分哈希值相等，说明前面一半是一样的。那么就在后面找不一样的地方。否则在前面找。找到以后，比较那个不一样的地方的大小就好了，复杂度$O(logN)$ 至于之前说的前缀和优化，我们发现[i-1-(j-i+1)+1,i-1]里面所有状态都可以直接转移，不需要一个一个计算，那么我们直接dp[i-1][j] - dp[i-1-(j-i+1)][j]就可以得到这些状态的结果的和了。但是在计算完dp[i][j]以后，要把dp[i-1][j]的值加进去，这样才是完整的维护前缀和。最后dp[n][n]就是答案。 代码如下
//
// Created by dhy on 19-1-20.
//
# include <iostream>
using namespace std;
const int MAXN = 5010;
const int mod = (int)1e9+7;
char c[MAXN];
int hsh[MAXN][MAXN];
long long dp[MAXN][MAXN];
int cmp(int a,int b){
if(c[a]==c[b])return 0;
if(c[a]<c[b])return -1;
else return 1;
}
int cmp1(int a,int b,int i,int j){//二分比大小
if(c[a]!=c[i])return cmp(a,i);
if(hsh[a][b]==hsh[i][j]){//can't transfer when equal
return 0;
}
int l = 1,r = b-a;
while(l<r){
int mid = (l+r)>>1;
if(hsh[a][a+mid]==hsh[i][i+mid])l = mid+1;
else r = mid;
}
return cmp(a+l,i+l);
}
int work(int l,int r){//这个地方是长度相等的时候即状态数计算，也是前缀和，只不过为了方便，打成函数
return ((dp[l][r]-dp[l-1][r])%mod+mod)%mod;
}
int n;
int main(){
cin>>n;
cin>>c+1;
for(int i = 1;i<=n;i++){//预处理把哈希处理出来
hsh[i][i] = c[i]-'0';
for(int j = i+1;j<=n;j++){
hsh[i][j] = (hsh[i][j-1]*10+c[j]-'0')%mod;
}
}
for(int i = 1;i<=n;i++)dp[1][i] = 1;
for(int i = 2;i<=n;i++){
for(int j = i;j<=n;j++){
int r = i-1,l = r-j+i;//可以直接转移的区间
dp[i][j] = ((dp[r][r]-dp[max(l,0)][r])%mod+mod)%mod;//转移，前缀和优化
if(l>=1&&cmp1(l,r,i,j)==-1){//对于长度相等的两个区间可否转移，小于即可转移
dp[i][j] = (dp[i][j]+work(l,r))%mod;
}
if(c[i]=='0')dp[i][j] = 0;//如果是0开头，就不是合法的状态，计数清空
dp[i][j] = (dp[i-1][j]+dp[i][j])%mod;//顺便维护前缀和
}
}
cout<<dp[n][n];//计算答案
return 0;
}
