记录编号	571673	评测结果	AAAAAAAAAA
题目名称	[NOI 1996]添加号	最终得分	100
用户昵称	lihaoze	是否通过	通过
代码语言	C++	运行时间	0.786 s
提交时间	2022-06-06 13:03:11	内存使用	7.17 MiB

#include <bits/stdc++.h>

using i64 = long long;

struct Bigint {
        std::vector<int> num;
        Bigint () {}
        Bigint (const char* rst) {
            int len = strlen(rst);
            for(int i = len - 1; i >= 0; -- i) num.emplace_back(rst[i] - 48);
        }
        Bigint (const int rst) {
            char tmp[100];
            sprintf(tmp, "%d", rst);
            *this = tmp;
        }
        Bigint operator + (const Bigint& rst) {
            Bigint ret;
            int t = 0;
            for(int i = 0; i < (int) num.size() || i < (int) rst.num.size() || t; ++ i) {
                if(i < (int) num.size()) t += num[i];
                if(i < (int) rst.num.size()) t += rst.num[i];
                ret.num.emplace_back(t % 10);
                t /= 10;
            }
            return ret;
        }
        Bigint operator * (int rst) {
            Bigint ret;
            int t = 0;
            for(int i = 0; i < (int) num.size() || t; ++ i) {
                if(i < (int) num.size()) t += num[i] * rst; 
                ret.num.emplace_back(t % 10);
                t /= 10;
            }
            while(ret.num.size() > 1 && !ret.num.back()) ret.num.pop_back();
            return ret;
        }
        friend bool operator < (Bigint lst, Bigint rst) {
            if(lst.num.size() > rst.num.size()) return false;
            else if(lst.num.size() < rst.num.size()) return true;
            else {
                for(int i = lst.num.size() - 1; i >= 0; -- i) {
                    if(lst.num[i] < rst.num[i]) return true;
                    if(lst.num[i] > rst.num[i]) return false;
                }
            }
            return false;
        }
        friend std::ostream& operator << (std::ostream& os, Bigint rst) {
            for(int i = rst.num.size() - 1; i >= 0; -- i) os << rst.num[i];
            return os;
        }
};

const int N = 201, M = 21;
char s[N];
int n, m;
Bigint f[N][M], g[N][N], mx;

// Bigint get(int l, int r) {
//     Bigint ret{0};
//     for (int i = l; i <= r; ++ i) ret = ret * 10 + (s[i] - '0');
//     return ret;
// }

int main() {
    freopen("exam4.in", "r", stdin); 
    freopen("exam4.out", "w", stdout);
    std::cin >> s + 1 >> m;
    n = strlen(s + 1);
    for (int i = 1; i <= n; ++ i) {
        g[i][i] = s[i] - 48;
        for (int j = i + 1; j <= n; ++ j) 
            g[i][j] = g[i][j - 1] * 10 + (s[j] - '0');
    }
    mx = g[1][n];
    for (int i = 1; i <= n; ++ i) 
        for (int j = 0; j <= std::min(i - 1, m); ++ j) {
            if (!j) { f[i][j] = g[1][i]; continue; }
            f[i][j] = mx;
            for (int k = j; k <= i; ++ k) 
                f[i][j] = std::min(f[i][j], f[k - 1][j - 1] + g[k][i]);
        }
    std::cout << f[n][m] << '\n';
    return 0;
}