Openjudge 最佳加法表达式 题解

最佳加法表达式

总时间限制:
1000ms
内存限制:
65536kB
描述
给定n个1到9的数字,要求在数字之间摆放m个加号(加号两边必须有数字),使得所得到的加法表达式的值最小,并输出该值。例如,在1234中摆放1个加号,最好的摆法就是12+34,和为36
输入
有不超过15组数据
每组数据两行。第一行是整数m,表示有m个加号要放( 0<=m<=50)
第二行是若干个数字。数字总数n不超过50,且 m <= n-1
输出
对每组数据,输出最小加法表达式的值
样例输入
2
123456
1
123456
4
12345
样例输出
102
579
15
提示
要用到高精度计算,即用数组来存放long long 都装不下的大整数,并用模拟列竖式的办法进行大整数的加法。
来源
Guo Wei

极其坑爹的一道题!要写高精度!坑人!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
using namespace std;
int m;
string numbers;
int strlen_n;
string store[51][51];
bool str_num_comp(const string & n1,const string & n2){//n1大为true,n2大为false
    if(n1.length()!=n2.length()){
        return n1.length()>n2.length();
    }else{
        int len=n1.length();
        for(int i=0;i<len;i++){
            if(n1[i]!=n2[i]){
                return n1[i]>n2[i];
            }
        }
        return false;
    }
}
string add_number(const string & n1,const string & n2){
    string result;
    int result_len,n3_len;
    result=n1;
    const string & n3=n2;
    result_len=result.length();
    n3_len=n3.length();
    for(int i=1;i<=n3_len;i++){
        result[result_len-i]+=n3[n3_len-i]-'0';
    }
    for(int i=result_len-1;i>0;i--){//最高位单独考虑
        while(result[i]>'9'){
            result[i]-=10;
            result[i-1]++;
        }
    }
    char c='0';
    if(result[0]>'9'){
        while(result[0]>'9'){
            c++;
            result[0]-=10;
        }
        result.insert(0,1,c);
    }
    return result;
}
string min_num(int m,int left){
    if(store[m][left]!="")return store[m][left];
    if(m==0){
        string result="";
        result.append(numbers,left,strlen_n-left+1);
        store[m][left]=result;
        return result;
    }else if(m>strlen_n-left){
        store[m][left]="99999999999999999999999999999999999999999999999999";
        return "99999999999999999999999999999999999999999999999999";
    }else{
        string str="99999999999999999999999999999999999999999999999999";
        for(int i=left;i<=strlen_n;i++){
            string s="";
            s.append(numbers,left,i-left+1);
            string s1=min_num(m-1,i+1);
            string s2;
            if(s.length()>s1.length()){
                s2=add_number(s,s1);
            }else{
                s2=add_number(s1,s);
            }
            if(str_num_comp(str,s2)){
                str=s2;
            }
        }
        store[m][left]=str;
        return str;
    }
}
int main(){
    ios::sync_with_stdio(false);
    while(cin>>m){
        for(int i=0;i<=50;i++){
            for(int j=0;j<=50;j++){
                store[i][j]="";
            }
        }
        cin>>numbers;
        strlen_n=numbers.length()-1;
        cout<<min_num(m,0)<<endl;
    }
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注