这是CF Goodbye 2015 的D题，当时我想了一个n^3的dp算法，肯定不能过，然后听到学长后缀数组的n^2log(n)写法，仰慕
最后打完比赛看到了t神的n^2写法，简直膜拜，直接省去了后缀数组，而且用一个sum由n^3变成了n^2,唉，经验无与伦比。Orz..
下面的代码就是我照着写的：
#include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #include<cstdlib> #include<cmath> #include<cstdlib> #include<vector> #include<queue> using namespace std; typedef long long LL; const int maxn=5005; const int mod=1e9+7; int dp[maxn][maxn]; int f[maxn][maxn]; char s[maxn]; bool cmp(int i,int j,int len) { if(f[i][j]>=len)return false; return s[i+f[i][j]]<s[j+f[i][j]]; } int main() { int n; 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])f[i][j]=f[i+1][j+1]+1; int ans=0; for(int i=1; i<=n; ++i) { int sum=0; for(int j=i; j<=n; ++j) { if(s[i]=='0') dp[i][j]=0; else if(i==1)dp[i][j]=1; else { int len=j-i+1; bool flag=0; if(i-len>=1&&cmp(i-len,i,len)) { flag=1; sum=(sum+dp[i-len][i-1])%mod; } dp[i][j]=sum; if(!flag&&i-len>=1) sum=(sum+dp[i-len][i-1])%mod; } if(j==n)ans=(ans+dp[i][j])%mod; } } printf("%d ",ans); return 0; }