CodeForces 611D:New Year and Ancient Prophecy DP + lcp

本文主要是介绍CodeForces 611D:New Year and Ancient Prophecy DP + lcp，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

传送门

题目描述

给一个n位数，要求将该n位数拆分成若干数字，且需满足：

数字的顺序要严格递增
数字都是正整数
没有前导零
求所有可能的方案数

分析

这道题写了好几天了2333
首先如何判断两个A和B谁大谁小
首先，如果A长度大于B长度，A大于B，反之亦然
如果AB长度相同，那么比较他俩的最长公共前缀，如果等于AB的长度，说明A等于B，如果不等于，那么就比较最强公共前缀的下一位即可

我们用数组dp[i][j]表示前i位中，如果最后一个数长度为j的情况分两种情况：

如果j前面那一段的长度小于j，那么表示可以肯定小于最后小于最后j位，可以直接进行转移(可以采用前缀和优化)
如果j前面那一段的长度等于j，那么就要判断是否合法，判断这两串的大小，然后进行状态转移

最后维护一下前缀和即可

代码

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <queue>
#include <cstring>
#define debug(x) cout<<#x<<":"<<x<<endl;
#define _CRT_SECURE_NO_WARNINGS
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
const int INF = 0x3f3f3f3f;
const int N = 5e3 + 10;
const ll mod = 1e9 + 7;
int lcp[N][N];
char str[N];
int n;
int sum[N][N];
ll dp[N][N];void LCP(){for(int i = n;i;i--)for(int j = n;j;j--)if(str[i] == str[j])lcp[i][j] = lcp[i + 1][j + 1] + 1;
}bool is(int x,int y){return str[x + lcp[x][y]] < str[y + lcp[x][y]];
}void solve(){for(int i = 0;i <= n;i++) sum[0][i] = 1;for(int i = 1;i <= n;i++){for(int j = 1;j <= i;j++){int len = i - j + 1;if(str[len] == '0') continue;dp[i][j] = (dp[i][j] + sum[len - 1][j - 1]) % mod;int s = len - j;if(s < 1) continue;if(is(s,len) && lcp[s][len] < j)dp[i][j] = (dp[i][j] + dp[len - 1][j]) % mod;}for(int j = 1;j <= n;j++)sum[i][j] = (sum[i][j - 1] + dp[i][j]) % mod;}}int main(){scanf("%d",&n);scanf("%s",str + 1);LCP();solve();ll ans = 0;for(int i = 1;i <= n;i++) ans = (ans + dp[n][i]) % mod;printf("%lld\n",ans);return 0;
}/**
*　　┏┓　　　┏┓+ +
*　┏┛┻━━━┛┻┓ + +
*　┃　　　　　　　┃
*　┃　　　━　　　┃ ++ + + +
*  ████━████+
*  ◥██◤　◥██◤ +
*　┃　　　┻　　　┃
*　┃　　　　　　　┃ + +
*　┗━┓　　　┏━┛
*　　　┃　　　┃ + + + +Code is far away from 　
*　　　┃　　　┃ + bug with the animal protecting
*　　　┃　 　 ┗━━━┓ 神兽保佑,代码无bug　
*　　　┃ 　　　　　　 ┣┓
*　　  ┃ 　　　　　 　┏┛
*　    ┗┓┓┏━┳┓┏┛ + + + +
*　　　　┃┫┫　┃┫┫
*　　　　┗┻┛　┗┻┛+ + + +
*/