云剪切板

// Problem: 4152:最佳加法表达式
// Contest: OpenJudge - 百练 - 练习
// URL: http://bailian.openjudge.cn/practice/4152/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>

using namespace std;

int m;
string str;
vector<int> x, y, ans[100][100];

vector<int> add(vector<int> a, vector<int> b) {
	int l = max(a.size(), b.size()), s = 0;
	if (a.size() < l) a.resize(l, 0);
	else if (b.size() < l) b.resize(l, 0);
	vector<int> c(l+1, 0);
	for (int i=0; i<l; ++i) {
		c[i] = a[i] + b[i] + s;
		s = c[i] / 10;
		c[i] %= 10;
	}
	c[l] = s;
	while (c.size()>1 && !c.back()) c.erase(c.end());
	return c;
}

bool cmp(const vector<int>& a, const vector<int>& b) {
	if (a.size() < b.size()) return 1;
	if (a.size() > b.size()) return 0;
	for (int i=0; i<a.size(); ++i)
		if (a[i] < b[i]) return 1;
	return 0;
}

vector<int> dfs(int d, int p) {
	if (ans[d][p].size() == 100) {
		if (d == m) {
			ans[d][p].clear(); ans[d][p].push_back(str[p]-'0');
			for (int i = p+1; i<str.size(); ++i) ans[d][p].insert(ans[d][p].begin(), str[i]-'0');
		} else {
			vector<int> tmp(1, 0), sum;
			for (int i=p; i<str.size()-m+d; ++i) {
				tmp.insert(tmp.begin(), str[i]-'0');
				// cout << d << ' ' << p << endl;
				// for (auto i = tmp.rbegin(); i!=tmp.rend(); ++i) cout << *i;
				// cout << endl;
				sum = add(tmp, dfs(d+1, i+1));
				if (cmp(sum, ans[d][p])) ans[d][p] = sum;
			}
		}
	}
	return ans[d][p];
}

int main() {
	while(cin >> m >> str) {
		for (int i=0; i<=m; ++i)
			for (int j=0; j<str.size(); ++j)
				ans[i][j].clear(), ans[i][j].resize(100, 9);
		dfs(0, 0);
		for (auto i = ans[0][0].rbegin(); i!=ans[0][0].rend(); ++i) cout << *i;
		cout << endl;
	}
	// x = vector<int>(5,7), y = vector<int>(7, 8);
	// res = add(x, y);
	// for (auto i = res.rbegin(); i!=res.rend(); ++i) cout << *i;
	return 0;
}