问题标题: 这是什么

描述

给定n个1到9的数字，要求在数字之间摆放m个加号(加号两边必须有数字），使得所得到的加法表达式的值最小，并输出该值。例如，在1234中摆放1个加号，最好的摆法就是12+34,和为36

输入有不超过15组数据

每组数据两行。第一行是整数m，表示有m个加号要放( 0<=m<=50)

第二行是若干个数字。数字总数n不超过50,且 m <= n-1输出对每组数据，输出最小加法表达式的值

使用string表示数字的高精度算法（可ＡＣ ):

#include<iostream>

#include<cstring>

#include<algorithm>

using namespace std;

int m;

string f[55], s;

 

string mins(string a, string b){

if(a=="INF")return b;

if(b=="INF")return a;

int i = 0;

while(a[i]=='0')i++;

a = a.substr(i);

i = 0;

while(b[i]=='0')i++;

b = b.substr(i);

int lena = a.size(),lenb = b.size();

if(lena > lenb){

return b;

}

else if(lena < lenb) {

return a;

 

}

for(int i = 0; i <= lena; i++){

if(a[i] == b[i])continue;

if(a[i]-'0' > b[i]-'0'){

return b;

}

return a;

}

return a;

}

 

string adds(string a, string b){

if(a=="INF" || b=="INF") return "INF";

string s = "";

int jw = 0,

i = a.size()-1,

j = b.size()-1,

k = 0;

while(i>=0 || j >= 0 || jw > 0){

int numa = (i>=0)?a[i--]-'0' : 0;

int numb = (j>=0)?b[j--]-'0' : 0;

int temp = numa+numb+jw;

s += (temp)%10 + '0';

jw = temp/10;

}

reverse(s.begin(), s.end());

return s;

}

 

int main(){

while(cin>>m){

cin>>s;

int n = s.size();

for(int i = 1; i <= n; i++)f[i] = "INF";

f[0] = "0";

m++;

for(int i = 1; i <= m; i++){

for(int j = n-m+i; j >= i; j--){

for(int k = i-1; k <=j-1; k++){

f[j] = mins(f[j], adds(f[k] , s.substr(k,j-k) ) );

}

}

}

cout<<f[n]<<endl;

}

}

 

 

 

使用long long 表示数字（最高支持18位十进制数字，此题测试数据不能AC）：

#include<iostream>

#include<cstring>

#include<algorithm>

using namespace std;

#define ll long long

ll has[55];

int m;

ll f[55];

 

ll kp(int a, int b){

ll ans = 1;

while(b){

if(b&1) ans *=a;

a*=a;

b>>=1;

}

return ans;

}

int main(){

while(cin>>m){

 

cin>>has[1];

int n;

for(n = 1; has[n]; n++){

has[n+1] = has[n]/10;

}

n--;

reverse(has+1, has+n+1);

memset(f,0x3f,sizeof(f));

f[0] = 0;

m++;

for(int i = 1; i <= m; i++){

for(int j = n-m+i; j >= i; j--){

for(int k = i-1; k <=j-1; k++)

f[j] = min(f[j], f[k] + has[j] - has[k]*kp(10,j-k));

}

}

cout<<f[n]<<endl;

}

}

毛润宇在2019-08-12 10:32:58追加了内容

这不是酷町堂题目，勿举报！！！

毛润宇在2019-08-12 10:33:59追加了内容

一句话，线性dp是算法中比较难的知识点