【题目描述】

　　给定一个很大的数字，有n位，你的任务就是将这个数字分割成若干段，分割的要求有2点：

　　1、分割后数字从左到右严格递增

　　2、每段分割数字不能有前导0 例如数字123434有8种分割方式，

　　分别为： 

　　　　"123434"
　　　　"1" + "23434"
　　　　"12" + "3434"
　　　　"123" + "434"
　　　　"1" + "23" + "434"
　　　　"1" + "2" + "3434"
　　　　"1" + "2" + "3" + "434"
　　　　"1" + "2" + "3" + "4" + "34"

　　统计有多少种分割方式，由于答案太大，对答案取模10^9+7。

这是今天比赛T3，也是唯一A掉的一道题...（虽然是非正解，但比赛时卡了一波常在0.1s内A了...出题人要卡的话会被卡成O(${n}^3$)...）

DP问题,我们用dp[i][len]表示第i为开始长度为n的答案的个数

状态转移：

dp[i][len]=$\Sigma$dp[i][len]+dp[i-k][k]

其中k在[1,len]之间，且要满足单调递增的关系

边界：

　　显然从1开始的任何长度都可以实现，所以dp[1][1...n]=1，其他为0

 

 1 #pragma GCC optimize("Ofast")
 2 #pragma GCC optimize(2)
 3 #include<cstdio>
 4 #include<queue>
 5 #include<iostream>
 6 #include<cstring>
 7 #include<algorithm>
 8 const int ha=1e9+7;
 9 using namespace std;
10 inline int read(){
11     int ans=0,f=1;char chr=getchar();
12     while(!isdigit(chr)){if(chr=='-') f=-1;chr=getchar();}
13     while(isdigit(chr)){ans=(ans<<3)+(ans<<1)+chr-48;chr=getchar();}
14     return ans*f;
15 }char s[5005];
16 int n,dp[5001][5001],ans;
17 inline bool Check(int i1,int len1,int i2,int len2){//判断和上一个比是否单调增
18     if(len1>len2) return 0;
19     if(len2>len1) return 1;
20     for(register int i=0;i<len1;++i){
21         if(s[i1+i]!=s[i2+i])
22             if(s[i1+i]>s[i2+i]) return 0;
23             else return 1;
24     }return 0;
25 }
26 int main(){
27     n=read(),scanf("%s",s+1);
28     for(register int i(1);i<=n;++i) dp[1][i]=1;
29     for(register int i(2);i<=n;++i){
30         if(s[i]==48) continue;//不能为前导0
31         for(register int len(1);i+len-1<=n;++len){//枚举长度
32             for(register int k(1);k<=min(len,i);++k)
33                 if(Check(i-k,k,i,len))
34                     dp[i][len]=(dp[i][len]+dp[i-k][k])%ha;
35             if(i+len-1==n) ans=(ans+dp[i][len])%ha;//累加答案
36         }
37     }cout<<(ans+1)%ha;//加1是因为dp[1][n]的值没有加上去过
38     return 0;
39 }
40 /*
41 6
42 123456
43 */