百练oj：最佳加法表达式，超过了long long范围，用自定义Bigint类解决

本文主要是介绍百练oj：最佳加法表达式，超过了long long范围，用自定义Bigint类解决，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：http://cxsjsxmooc.openjudge.cn/2021t2summer/014/
按照老师的思路写了代码，思路详见代码注释

#include <bits/stdc++.h>
#define mem(a, n) memset(a, n, sizeof(a))
#define max_len 52 //bigint类中最多储存位数+1
using namespace std;
//只支持正数和加法操作
class bigint
{
private://数字采用右对齐方式，即最小位在num[max_len-1],前面以0填充int num[max_len];int len;//表示num中最左端数字的下标public:void init()//初始化函数{len=max_len;mem(num,0);}bigint(){init();};bigint(char const s[]){init();for (int i = strlen(s) - 1; i >= 0; i--)num[--len] = s[i] - 48;}//重载加法运算bigint operator+(const bigint &b){bigint result;int carry = 0; //表示进位int l = len < b.len ? len : b.len;//取两数中较大那个数的最左端下标for (int i = max_len - 1; i >= l; i--)//从右往左运算{result.num[i] = num[i] + b.num[i] + carry;if (result.num[i] > 9){result.num[i] -= 10;carry = 1;}elsecarry = 0;}//判断最左端一位是否需要进一if (carry == 1)result.num[--l] = 1;result.len = l;return result;}//重载输出符号friend ostream &operator<<(ostream &out, const bigint b){for (int i = b.len; i <= max_len - 1; i++){out << b.num[i];}return out;}//重载输出符号friend istream &operator>>(istream &in, bigint &b){b.init();char s[max_len];in >> s;b = bigint(s);return in;}//重载小于运算符bool operator<(const bigint &b){if (len < b.len)return false;if (len > b.len)return true;for (int i = len; i <max_len; i++){if (num[i] > b.num[i])return false;if (num[i] < b.num[i])return true;}return false;}//重载大于运算符bool operator>(const bigint &b){if (len > b.len)return false;if (len < b.len)return true;for (int i = len; i <max_len; i++){if (num[i] < b.num[i])return false;if (num[i] > b.num[i])return true;}return false;}//取x到y位之间的数,这里的xy以正常顺序来计算//x=1表示最高位bigint subnum(int x, int y) {bigint result;//将x,y转换为类内数字存储的顺序x = x + len - 1;y = y + len - 1;for (int i = y; i >= x; i--){result.num[--result.len] = num[i];}return result;}//将数字设置为很大（用于找最小值）void set_inf(){len=1;num[len]=9;}//返回数字位数int size(){return max_len - len;}
};
bigint dp[max_len][max_len];  //dp[x][y]在前x个数字中插入y个加号的最小结果
bigint num[max_len][max_len]; //num[x][y]保存输入中x-y位之间的数字组成的数//将输入数字的各段取出数字存入num数组中
void sub_num(bigint &in)
{for (int i = 1; i <= 50; i++){for (int j = i; j <= 50; j++){num[i][j] = in.subnum(i, j);}}
}void solve(int len, int n)
{for (int i = 1; i <= len; i++){dp[i][0] = num[1][i];}//i表示加号个数for (int i = 1; i < n; i++){//j表示前j个数字中插入i-1个+号for (int j = i+1; j <= len; j++){dp[j][i].set_inf();//k表示分割点for (int k = i; k < j; k++){if (dp[j][i] > dp[k][i - 1] + num[k + 1][j])dp[j][i] = dp[k][i - 1] + num[k + 1][j];}}}//最后一步的时候无需将所有长度都计算出，只需计算dp[len][n]即可dp[len][n].set_inf();for (int k = n; k < len; k++){if (dp[len][n] > dp[k][n - 1] + num[k + 1][len])dp[len][n] = dp[k][n - 1] + num[k + 1][len];}//将结果输出cout<<dp[len][n]<<endl;
}int main()
{int n;while (cin >> n){bigint in;cin >> in;if(n){sub_num(in);solve(in.size(), n);}else cout<<in<<endl;}return 0;
}