AC自动机

HDU 3341 Lost’s revenge

Posted on

AC自动机 + 变进制状压DP

看题目的 discuss 都说会卡数据,但我还是 1500ms A了。虽然变进制的思路并不是我的……

最近有点懒得写博客了呀

题意:
还是基因碱基对背景。
给你几个模式串,再给你一个匹配串,允许你对匹配串重新排列,要求重新排列后跟模式串匹配的最大数量。

思路:
如果再加个权值,那就是DP套DP了,(误……
本质上还是一个计数DP,考虑状压,但是给定的匹配串长度上限为 40 ,如果开一个状态+节点的 5维数组,会炸内存。
考虑到将节点的 4 维压缩,因为 40 的实际状态数最多是 4 个碱基数量相同的时候。
也就是10 \times 10 \times 10 \times 10,内存与复杂度均可以承受。

AC Code

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary))

using namespace std;
const int max_n = 505;
const int max_c = 4;

int num[4];
int change[130];

struct Aho {
    int next[max_n][max_c], fail[max_n], end[max_n];
    int root, size;
    queue<int> que;

    int newNode()
    {
        for (int i = 0; i < max_c; i++)
            next[size][i] = 0;
        end[size++] = 0;
        return size - 1;
    }

    inline void init()
    {
        size = 1;
        root = newNode();
    }

    void insert(char str[])
    {
        int len = strlen(str), now = root;
        for (int i = 0; i < len; i++) {
            int c = change[(int)str[i]];
            if (!next[now][c])
                next[now][c] = newNode();
            now = next[now][c];
        }
        end[now]++;
    }

    void build()
    {
        fail[root] = root;
        for (int i = 0; i < max_c; i++)
            if (!next[root][i])
                next[root][i] = root;
            else {
                fail[next[root][i]] = root;
                que.push(next[root][i]);
            }
        while (!que.empty()) {
            int now = que.front();
            que.pop();
            end[now] += end[fail[now]];
            for (int i = 0; i < max_c; i++)
                if (!next[now][i])
                    next[now][i] = next[fail[now]][i];
                else {
                    fail[next[now][i]] = next[fail[now]][i];
                    que.push(next[now][i]);
                }
        }
    }

    int dp[max_n][11 * 11 * 11 * 11 + 5];
    int query()
    {
        int res = 0, bit[4];
        memset(dp, -1, sizeof dp), dp[root][0] = 0;
        bit[3] = 1;
        rrange(i, 1, 3) bit[i - 1] = (num[i] + 1) * bit[i];
        range(A, 0, num[0]) range(T, 0, num[1]) range(C, 0, num[2]) range(G, 0, num[3])
        {
            int sta = A * bit[0] + T * bit[1] + C * bit[2] + G;
            range(cur, root, size - 1) if (dp[cur][sta] >= 0) for (int i = 0; i < 4; i++)
            {
                if (i == 0 && A == num[0]) continue;
                if (i == 1 && T == num[1]) continue;
                if (i == 2 && C == num[2]) continue;
                if (i == 3 && G == num[3]) continue;
                dp[next[cur][i]][sta + bit[i]] = max(dp[next[cur][i]][sta + bit[i]], dp[cur][sta] + end[next[cur][i]]);
            }
        }
        int fnl = 0;
        each(i,4) fnl += num[i] * bit[i];
        range(i,root,size - 1) res = max(res, dp[i][fnl]);
        return res;
    }
} aho;

char buf[50];

int main()
{
    change[(int)'A'] = 0, change[(int)'T'] = 1, change[(int)'C'] = 2, change[(int)'G'] = 3;
    int n, cas = 0;
    while (scanf("%d", &n) != EOF && n) {
        memset(num, 0, sizeof num);
        aho.init();
        for (int i = 0; i < n; i++) {
            scanf("%s", buf);
            aho.insert(buf);
        }
        aho.build();
        scanf("%s", buf);
        int len = strlen(buf);
        for (int i = 0; i < len; i++)
            num[change[(int)buf[i]]]++;
        printf("Case %d: %d\n", ++cas, aho.query());
    }
    return 0;
}
DP套DP

HDU 4899 Hero meet devil

Posted on

训练赛的DP套DP,关于DP套DP,以前记得好像做过一道。题目本身十分巧妙,但貌似不是很多。可能不是很好出题吧。
所谓DP套DP,就是我DP所需的状态也需要额外的DP求出来。简单说,就是我需要DP两次,在第一次的DP结果上再DP一次。

题意:
给你一个DNA序列,再给你一个固定长度,问你在这个长度下的所有序列中,与给定的DNA序列的LCS分别为[0,len(DNA)]的序列数量。

思路:
因为数据很小,我们可以考虑用状压做。
对于当前长度的一个最优状态,如果增加一个字符,它的下一个状态就需要加上当前状态的序列数量。
这是一个非常常见的计数DP。

但是已知当前状态,无法直接得出下一个状态,而这个就是我们需要嵌套在内的DP了。
我们枚举每一个状态,在枚举每一个字符,使其插入当前状态,再转移它的LCS,最后再统计一下就可以了。
而统计方法是如果当前位置的LCS与前一位置的LCS不同,则说明这个位置与LCS的DNA序列匹配。

虽然我说的很简洁,但是我当时也是想了好长时间……

AC Code

#include <bits/stdc++.h>

using namespace std;

const int mod = 1e9 + 7;
const int maxl = 16;
const int maxs = 1 << maxl;

char key[] = "ATCG";
size_t len;
int dp[2][maxs], ans[maxl];
int nexts[maxs][4];
int pre, cur = 1;
int cnt[maxl], lcs[maxl];

char str[maxl];

inline void add(int &a, int b) {
    a = a + b >= mod ? a + b - mod : a + b;
}

void init() {
    for (int sta = 0; sta < (1 << len); sta++) {
        for (int i = 1; i <= len; i++)
            cnt[i] = cnt[i - 1] + (sta >> (i - 1) & 1);
        for (int k = 0; k < 4; k++) {
            for (int i = 1; i <= len; i++) {
                if (str[i] == key[k])
                    lcs[i] = cnt[i - 1] + 1;
                else
                    lcs[i] = max(lcs[i - 1], cnt[i]);
            }
            int &tmp = nexts[sta][k] = 0;
            for (int i = 1; i <= len; i++)
                tmp |= ((lcs[i] != lcs[i - 1]) << (i - 1));
        }
    }
    memset(dp, 0, sizeof dp);
    memset(ans, 0, sizeof ans);
}

int main() {
    int T, n;
    scanf("%d", &T);
    while (T--) {
        scanf("%s %d", str + 1, &n);
        len = strlen(str + 1);
        init();
        dp[pre][0] = 1;
        for (int i = 0; i < n; i++) {
            memset(dp[cur], 0, sizeof dp[cur]);
            for (int sta = 0; sta < (1 << len); sta++)
                for (int j = 0; j < 4; j++)
                    add(dp[cur][nexts[sta][j]],dp[pre][sta]);
            cur ^= 1, pre ^= 1;
        }
        for (int sta = 0; sta < (1 << len); sta++)
            add(ans[__builtin_popcount(sta)], dp[pre][sta]);
        for (int i = 0; i <= len; i++)
            printf("%d\n", ans[i]);
    }
    return 0;
}
状压DP

HDU 4628 Pieces

Posted on

CLS的状压DP系列……
然而实际上也算是一道简单题,但是我并没有立刻写出来。
不知道为什么,每次我尝试这用已知最优状态去推其他状态都是错的……
然而用当前状态之前的状态来推当前状态却是对的。

顺便学习了一个,二进制子集的枚举方法。for ( int sta = state ; sta ; sta = (sta - 1) & state )
学了这么久状压居然连这个都知道真是醉了……

题意:
给你一个字符串,每次只能取走一个回文串,问最少取几次。

思路:
先预处理出所有状态是否为回文串,并使得 这个状态取值为 1 。
枚举每个状态,再枚举它的所有子集。
状态转移方程 为 dp[sta] = min(dp[sta], dp[sta ^ s] + dp[s] )

AC Code

#include <bits/stdc++.h>

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary))

using namespace std;

const int maxn = 16;
const int inf = 0x3f3f3f3f;

char str[maxn];
int dp[1 << maxn];
int len;

void judge(int sta)
{
    if (dp[sta] != inf)
        return;
    int l = 0, r = len - 1;
    while (l < r) {
        while ((sta & (1 << l)) == 0 && l < len - 1)
            l++;
        while ((sta & (1 << r)) == 0 && r > 0)
            r--;
        if (str[l] != str[r]) {
            dp[sta] = inf + 1;
            return;
        }
        l++, r--;
    }
    dp[sta] = 1;
}

int main()
{
    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%s", str);
        len = strlen(str);
        int maxs = (1 << len) - 1;
        fill(dp, 0x3f), dp[0] = 0;
        range(sta, 1, maxs) each(j, len) judge(sta | (1 << j));
        range(sta, 1, maxs)
        {
            for (int s = sta; s; s = (s - 1) & sta)
                dp[sta] = min(dp[sta], dp[sta ^ s] + dp[s]);
        }
        printf("%d\n", dp[maxs]);
    }
    return 0;
}
树形DP

CodeForces 842 C Ilya And The Tree

Posted on

树上的选择性DP……
不是很懂其他人的做法,偶然间看到有人用ruby A了,我也就用ruby敲了一蛤
速度有点玄……

题意:
给你一棵树,每个节点都有权值,要你求每个节点到根节点所形成的树链 gcd。
其中每条树链都可以选择一个节点使得权值变为 0 。

思路:
感觉这就是裸题……
只不过就是把数组改成树上了而已。
用一个栈或者队列去遍历这棵树,对于每个节点是否变0都考虑一下就好了……

AC Code

#!/usr/bin/env ruby
# encoding: utf-8
n = gets.to_i
a = gets.split.map(&:to_i)
g = Array.new(n) {[]}

(n-1).times do
    u, v = gets.split.map(&:to_i)
    u, v = u-1, v-1
    g[u] << v
    g[v] << u
end

def GCD(a, b) return b == 0 ? a : GCD(b, a%b) end

dp = Array.new(n) { Array.new(2) { [] } }
dp[0] = [[a[0]], [0]]
par = [-1]*n

st = [0]
until st.empty?
    u = st.pop
    g[u].each do |v|
        next if v == par[u]
        par[v] = u
        st.push(v)
        dp[v][0] += dp[u][0].map{|x| GCD(x,a[v])}
        dp[v][1] += dp[u][0]
        dp[v][1] += dp[u][1].map{|x| GCD(x,a[v]) }
        2.times do |i|
            dp[v][i].uniq!
        end
    end
end

print a[0]
for u in 1...n do
    print " #{dp[u][1].max}"
end
简单DP

HDU 6143 Killer Names

Posted on

昨天的多校应该是团队合作最失败的一次……

一开始过题人数最多的那道题许颂嘉没去想,只能我自己上了,第一直觉就是DP,但这个状态转移真的想了我好久好久,但想出来后又觉得是非常显然的……

后来不知道什么时候许学姐来想这题了,估计是急了,也没跟我说,然后就是两个人单独想题的局面,还瞒着我敲了一发容斥……是的,一个队里两个人同时用两种算法在想同一题。这是团队赛最忌讳的。
也可以说是最愚蠢的。

之后敲完之后雨情学姐又给了我一个错误数据,先是打乱我的思路,然后debug了将近一个小时,发现数据错误之后,把最开始的代码交了一发就秒了……

不想多说什么,这场明明还有一道很简单的细心题,当时急了,没发现重点。和一道几乎是AC自动机入门题的题,没看。

我特么 心如刀割。

题意:
给你一个长度

*** QuickLaTeX cannot compile formula:
n\和字符数量\( m

*** Error message:
Undefined control sequence \宍
leading text: $n\半

,让你组成两个字符串,两个字符串两两不能有统一字符。

思路:
标程是容斥,我不会,这题提供DP解法。
dp[ len ] [ num ] 表示长度为len 的字符串并且有num个字符的数量。
那么我现在只考虑一个字符串,它的长度固定为n,我用 num 个字符去组成它,那么对于剩下可选的m - num个字符,任意组成另一个字符串。
这里所谓另一个字符串是可以直接求并且很好求的,就是( m - num )^n自己去体会啦
dp [ len ] [ num ]可以通过如下转移方程求解。

dp[ len ] [ num ] = dp[ len - 1 ] [ num - 1 ] \times ( m - num + 1 ) + dp [ len - 1 ] [ num ] \times num

略加思考就能体会到这个转移方程的正确性,这里就不说了。

AC Code

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<algorithm>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<vector>
using namespace std;
typedef long long ll;

const int mod = 1e9+7;
const int maxn = 2e3+5;

int n,m;
ll dp[maxn][maxn];

ll fastPow(ll n,ll m)
{
    ll ans=1;
    while (m)
    {
        if (m&1)
            ans=ans*n%mod;
        n=n*n%mod;
        m>>=1;
    }
    return ans;
}

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d %d",&n,&m);
        for(int len=1; len<=n; len++)
            dp[len][1]= m ;
        for(int num=2; num<=m; num++)
            dp[1][num] = 0;
        for(int len=2; len<=n; len++)
            for(int num=2; num<=m; num++)
                dp[len][num] = ((dp[len-1][num-1]*(m-num+1))%mod+(dp[len-1][num]*num)%mod)%mod;
        ll ans = 0;
        for(int num=1; num<m; num++)
            ans = (ans+dp[n][num] * fastPow(m-num,n))%mod;
        printf("%lld\n",ans);
    }
    return 0;
}
状压DP

BZOJ 4197 寿司晚宴

Posted on

上一场多校一道状压DP的原题。
那我肯定是去做原题啦。

多校的时候我还觉得这肯定是许学姐的锅,没想到居然能转化成状压。

题意:
中文题面,给你[ 2, n ] 这几个数,要你各找两组数字,两组数字之间两两互质。
n 最大为500,问组合数量。

思路:
考虑数据 n 非常小,在 \sqrt 500以内的质数只有8个,而大于\sqrt 500的大元素只可能为一个,那么我们把相同的大元素放在一起处理,开一个二维数组表示这个大元素在两组中的哪一组,而对于小元素,可以用状态压缩来表示两组数字各自包含那几个质数。最后累加的时候让两个状态不重叠即可。

代码中 dp [ k ] [ a ] [ b ] [ c ] 表示 前k个元素中 第一组数包含的小质数状态为a ,第二组数包含的小质数状态为b ,大质数为在第一组0 ,或者在第二组1 的组合数量。
dp过程中,可以通过类似背包处理,反向计算,省掉一维。

f [ k ] [ a ] [ b ] 表示前k 个元素中,第一组包含的小质数状态为a,第二组包含的小质数状态为 b 的组合数量。

因为dp数组包含了当前大质数的分配状态。所以在处理不同大质数的时候理所当然地要将 dp数组重置。方法就是用f [ a ] [ b ]进行汇总,再分配。
在汇总的时候格外要注意的是,必须减去一个以前的f [ a ] [ b ],因为 dp数组在大质数分配的两个状态中都记录了以前的f [ a ] [ b ],也就是在此之上没有加上任何元素的组合数。汇总的时候是多加一次的,这应该比较容易理解。

而状态转移方程是最好理解,我就不多说了 虽然不是我想出来的

AC Code

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary))

using namespace std;
typedef long long ll;
const int maxn = 510;
const int maxc = 1 << 8;

ll dp[maxc][maxc][2], f[maxc][maxc];
ll n, mod;
int pri[10] = { 2, 3, 5, 7, 11, 13, 17, 19, 0, 0 };

struct node {
    int state;
    int big;
    bool operator<(const node& a) const { return big < a.big; }
} num[maxn];

void init()
{
    range(i, 2, n)
    {
        int x = i, v;
        each(j, 8) if (x % (v = pri[j]) == 0)
        {
            while (x % v == 0)
                x /= v;
            num[i].state |= (1 << j);
        }
        num[i].big = x;
    }
    sort(num + 2, num + n + 1);
    f[0][0] = 1;
}

int main()
{
    scanf("%lld %lld", &n, &mod);
    init();
    range(i, 2, n)
    {
        if (i == 2 || num[i].big == 1 || num[i].big != num[i - 1].big)
            reach(j, maxc) reach(k, maxc) dp[j][k][0] = dp[j][k][1] = f[j][k];
        reach(j, maxc) reach(k, maxc)
        {
            if ((num[i].state & j) == 0)
                dp[j][k | num[i].state][1] = (dp[j][k | num[i].state][1] + dp[j][k][1]) % mod;
            if ((num[i].state & k) == 0)
                dp[j | num[i].state][k][0] = (dp[j | num[i].state][k][0] + dp[j][k][0]) % mod;
        }
        if (i == n || num[i].big == 1 || num[i].big != num[i + 1].big)
            reach(j, maxc) reach(k, maxc) f[j][k] = (dp[j][k][0] + dp[j][k][1] - f[j][k] + mod) % mod;
    }
    ll ans = 0;
    reach(i, maxc) reach(j, maxc) if ((i & j) == 0) ans = (ans + f[i][j]) % mod;
    printf("%lld\n", ans);
    return 0;
}
区间DP

区间DP入门 —— 三类经典问题

Posted on

例行废话

大概是前天试着去入门区间DP,中间穿插了很多其他题目,今天勉强入门并多写了几题。

又被goubi带鱼笑了,shit!
有些时候我自己也会觉得写一些入门的东西会有点浪费时间……
但我又想了想,应该说是每个人写博文的目的不同吧。
像我这种小网站,我也不渴求能帮到多少人,只是记录一下自己的成长罢了。

三类经典问题

区间DP被goubi带鱼说是最简单的DP,因为它是有套路可循的。
这个套路就是用小区间推出大区间。是的,这个套路就是这么简单,其他的还是考虑状态与个人思维了。
而小区间推出大区间的方法自然是按照区间长度不断向后DP,每次将所有长度相同的区间长度推出。
一般来说,把这个这个思维熟练了,再学一个四边形优化,区间DP就可以毕业了。goubi带鱼如是说

而关于三类经典问题,大多数区间DP都可以通过转换得到这三类基础模型。当然我也是听别人说啦,我也才刚入门啊

石子归并

传送门

题意:

给你一排石子,你只能将相邻的石子合成一堆,花费为两堆石子的重量和。问如何合并,花费最小。

思路:

如果去掉相邻石子才能合并的限制,那就是一个裸的哈夫曼树。
而考虑这个限制的话,就得用区间DP的思想了。

一开始我觉得,裸题,直接区间值不断相加就好了。事实上不行,我并没有考虑好区间所表示的含义。
每个区间就是每个状态,状态的意义在DP中的位置非常重要。

每个区间的确是合并所得区间的最小花费,但是还需要考虑一个合并花费,而合并花费其实就是这个区间的石子总数。因此,问题得到了解决。

AC Code

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <numeric>
#include <queue>
#include <string>

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary))

using namespace std;

typedef long long ll;

const int inf = 0x3f3f3f3f;
const int maxn = 205;
int dp[maxn][maxn];
int ary[maxn], sum[maxn];

int main()
{
    int n;
    while (scanf("%d", &n) != EOF) {
        fill(dp, 0), fill(sum, 0);
        range(i, 1, n) scanf("%d", ary + i), sum[i] = sum[i - 1] + ary[i];
        range(len, 2, n)
        {
            for (int l = 1, r = len; r <= n; l++, r++) {
                dp[l][r] = inf;
                range(i, l, r - 1) dp[l][r] = min(dp[l][r], dp[l][i] + dp[i+1][r] + sum[r] - sum[l-1]);
            }
        }
        printf("%d\n", dp[1][n]);
    }
    return 0;
}

括号匹配

传送门

题意:

给你一个括号序列,要你找出,最长的满足两两匹配的子序列。

思路:

这个较为简单,基本思路是找出可以扩展的状态,之后就是区间合并找最小了。

这里可扩展的状态为 左右两边是否能组成成型的括号,如果能,则 dp[ l ] [ r ] = dp [ l + 1 ] [ r - 1] + 2 ,否则, dp [ l ] [ r ]  = dp [ l + 1 ] [ r - 1 ]

AC Code

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <numeric>
#include <queue>
#include <string>

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary))

using namespace std;

typedef long long ll;
const int maxn = 105;
int dp[maxn][maxn];

char str[maxn];

int main()
{
    int len;
    while (scanf("%s", str) != EOF && strcmp(str, "end") != 0) {
        len = strlen(str), fill(dp, 0);
        each(i, len)
        {
            for (int l = 0, r = i; r < len; l++, r++) {
                if ((str[l] == '(' && str[r] == ')') || (str[l] == '[' && str[r] == ']'))
                    dp[l][r] = dp[l + 1][r - 1] + 2;
                range(k, l + 1, r - 1) dp[l][r] = max(dp[l][k] + dp[k][r], dp[l][r]);
            }
        }
        printf("%d\n", dp[0][len - 1]);
    }
    return 0;
}

整数划分

传送门

题意:

给你一个整数 n ,要你从中间插入 m - 1 个乘号,使得所得结果最大。

思路:

套路基本是一致的,只不过这里的区间是乘号的数量。
dp[len][num] 表示从 [ 0, len ] 中放 num 个乘好对应的最大值。
转移方程如下:
dp [ i ] [ j ]  = \max (dp [ i ] [ j ] , dp [ k ] [ j-1 ] * a [ k+1 ] [ i ] )

AC Code

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <numeric>
#include <queue>
#include <string>

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary))

using namespace std;

typedef long long ll;

const int inf = 0x3f3f3f3f;
const int maxn = 25;

int m;
char num[maxn];
ll dp[maxn][maxn], a[maxn][maxn];

int main()
{
    int T;
    scanf("%d", &T);
    while (T--) {
        fill(dp, 0);
        scanf("%s %d", num, &m);
        int len = strlen(num);
        each(i, len) a[i][i] = num[i] - '0';
        range(i, 1, len - 1) for (int l = 0, r = i; r < len; l++, r++) {
            a[l][r] = a[l][r - 1] * 10 + num[r] - '0';
        }
        each(i, len) dp[i][1] = a[0][i];
        range(l, 2, m) range(i, l-1, len - 1)
        {
            each(pos, i) dp[i][l] = max(dp[i][l], dp[pos][l - 1] * a[pos + 1][i]);
        }
        printf("%lld\n", dp[len - 1][m]);
    }
    return 0;
}