Codeforces 611D - New Year and Ancient Prophecy (划分数字字符串、单调递增)

Jan 6, 2016


题意

给一串字符串,问有几种方式划分,使得没有前导零并且每个部分单调递增。

思路

dp[i][j]表示第i个位置,最后一段长度为j的方案数。 $dp[i][j] = \sum_{k=1}^{j-1} dp[i-j][k] + dp[i-j][j]\ \text{(if str[i-2*j+1][j] < str[i-j+1][j])}$

然后一边递推一边维护一个前缀和数组即可。

判断两个字符串数组大小用最长公共前缀去判断,这里有点神奇。

代码

#include <stack>
#include <cstdio>
#include <list>
#include <cassert>
#include <set>
#include <fstream>
#include <iostream>
#include <string>
#include <ostream>
#include <vector>
#include <queue>
#include <functional>
#include <cstring>
#include <algorithm>
#include <cctype>
//#pragma comment(linker, "/stack:102400000,102400000")
#include <string>
#include <map>
#include <cmath>
#define LL long long
#define ULL unsigned long long
#define SZ(x) (int)x.size()
#define lowbit(x) ((x) & (-x))
#define MP(a, b) std::make_pair(a, b)
#define MS(p, num) memset(p, num, sizeof(p))
#define X first
#define Y second
#define ROP freopen("input.txt", "r", stdin);
#define mid(a, b) (a + ((b - a) >> 1))
#define LC rt << 1, l, mid
#define RC rt << 1|1, mid + 1, r
#define LRT rt << 1
#define RRT rt << 1|1
#define FOR(i, a, b) for (int i=(a); (i) < (b); (i)++)
#define FOOR(i, a, b) for (int i = (a); (i)<=(b); (i)++)
const double pi = acos(-1.0);
const int INF = 0x3f3f3f3f;
const double eps = 1e-8;
const int MAXN = 5000 + 10;
const int MOD = 1e9 + 7;
const int dir[][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
const int seed = 131;
int cases = 0;
typedef std::pair<int, int> pii;
 
int cnt[MAXN][MAXN], dp[MAXN][MAXN], sum[MAXN][MAXN];
char str[MAXN];
int n;
 
void get_lcp()
{
    for (int i = n; i >= 1; i--)
        for (int j = n; j >= i + 1; j--) if (str[i] == str[j])
            cnt[i][j] = cnt[i + 1][j + 1] + 1;
}
 
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++) if (str[i - j + 1] != '0')
        {
            dp[i][j] += sum[i - j][j - 1];
            if (dp[i][j] > MOD) dp[i][j] -= MOD;
            int l = i - 2*j + 1, r = i - j + 1;
            if (l < 1) continue;
            if (cnt[l][r] < j && str[l + cnt[l][r]] < str[r + cnt[l][r]])
            {
                dp[i][j] += dp[i - j][j];
                if (dp[i][j] > MOD) dp[i][j] -= MOD;
            }
 
        }
        for (int j = 1; j <= n; j++)
        {
            sum[i][j] = sum[i][j - 1] + dp[i][j];
            if (sum[i][j] > MOD) sum[i][j] -= MOD;
        }
    }
    LL ans = 0;
    for (int i = 1; i <= n; i++) ans = (ans + dp[n][i]) % MOD;
    printf("%I64d\n", ans);
}
 
int main()
{
    //ROP;
    scanf("%d", &n);
    scanf("%s", str + 1);
    get_lcp();
    solve();
    return 0;
}