当前位置 : 主页 > 编程语言 > 其它开发 >

AtCoder Beginner Contest 249 E - RLE // 动态规划 + 前缀和优化

来源:互联网 收集:自由互联 发布时间:2022-05-30
AtCoder:动态规划,前缀和优化 传送门: E - RLE (atcoder.jp) 题意: 求满足原长为N且转换后长度严格小于N条件的小写字母组成的字符串的数量,输出时对P取模。 其中,转换规则为,将连
AtCoder Beginner Contest 249 E - RLE // 动态规划 + 前缀和优化 AtCoder:动态规划,前缀和优化

传送门:E - RLE (atcoder.jp)

 

题意:

求满足原长为N且转换后长度严格小于N条件的小写字母组成的字符串的数量,输出时对P取模。

其中,转换规则为,将连续相同的字串替换为“字符数量+字符”,如aaa替换为3a。

 

思路:

  • 状态表示:

    fi,j:原长为i且转换后长度为j的字符串的数量。

  • 状态转移:

  初始化:将仅包含一种字符的所有字符串进行初始化。

  转移:先考虑暴力做法:fi,j:考虑最后一段连续相同字串的长度为k,其替换后的字串长度为u,那么fi,j = 25 * ∑ fi-k,j-u注意到,u的取值最多仅有 { 2,3,4,5 },那么进行前缀和优化一下,计算时就可以由枚举所有k变为枚举所有u, 整体复杂度由O(N3)变为O(N2lgN)。

 

代码参考:

//Jakon:dp + 前缀和优化
#include <bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 3010, M = 4321;

int n, p;
LL dp[N][M], pres[N][M];
// dp[i][j]:原串长度为i,转化后长度为j的方案数

int cal(int x)
{
    int res = 2;
    if(x >= 10) ++ res;
    if(x >= 100) ++ res;
    if(x >= 1000) ++ res;
    return res;
}

int main()
{
    cin >> n >> p;

    for(int i = 1; i <= n; i++) dp[i][cal(i)] = 26;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= min(i * 2, M - 1); j++) {
            for(int mi = 1, k = 2; mi < i && k < j; mi *= 10, k++) {
                int l = max(0, i - mi * 10), r = i - mi;
                dp[i][j] = (dp[i][j] + 25 * (pres[r][j-k] - pres[l][j-k] + p)) % p;
            }
            pres[i][j] = (pres[i - 1][j] + dp[i][j]) % p;
        }
    }
    
    LL ans = 0;
    for(int i = 0; i < n; i++) ans = (ans + dp[n][i]) % p;
    cout << ans << endl;

    return 0;
}

 

【本文来自:日本服务器 http://www.558idc.com/jap.html 复制请保留原URL】
网友评论