Quicksum -SilverN

quicksum

Given a string of digits, find the minimum number of additions required for the string to equal some target number. Each addition is the equivalent of inserting a plus sign somewhere into the string of digits. After all plus signs are inserted, evaluate the sum as usual. For example, consider the string "12" (quotes for clarity). With zero additions, we can achieve the number 12. If we insert one plus sign into the string, we get "1+2", which evaluates to 3. So, in that case, given "12", a minimum of 1 addition is required to get the number 3. As another example, consider "303" and a target sum of 6. The best strategy is not "3+0+3", but "3+03". You can do this because leading zeros do not change the result.

Write a class QuickSums that contains the method minSums, which takes a String numbers and an int sum. The method should calculate and return the minimum number of additions required to create an expression from numbers that evaluates to sum. If this is impossible, return -1.

example:

"382834"

100

Returns: 2

There are 3 ways to get 100. They are 38+28+34, 3+8+2+83+4 and 3+82+8+3+4. The minimum required is 2.

Constraints

- numbers will contain between 1 and 10 characters, inclusive.

- Each character in numbers will be a digit.

- sum will be between 0 and 100, inclusive.

- the string will be shorter than 100 bit.

Examples

"99999"

Returns: 4

In this case, the only way to achieve 45 is to add 9+9+9+9+9. This requires 4 additions.

"0123456789" 01+2+3+4+5+6+7+8+9

Returns: 8

一般的DFS解法：

（下附代码中并没有写无解时输出-1的部分，懒得补了233）

 1 /*Silver_N quicksum*/
 2 #include<algorithm>
 3 #include<iostream>
 4 #include<cmath>
 5 #include<cstdio>
 6 using namespace std;
 7 int n[500];//每个数字 
 8 int re[200][200];
 9 int ct=0;//总字符数 
10 int mini=10000;//最小解 
11 int m;//需求数 
12 int ansum=0;
13 int ssum(int s,int t){//截取字符串的函数，通过记忆化避免重复计算 
14     int i,j;
15     if(re[s][t])return re[s][t];
16     //else begin
17     int x=0;
18     for(i=s;i<=t;i++){
19         x=x*10+n[i];
20     }
21     re[s][t]=x;
22     return x;
23     //end
24 }
25 void read1(){//数据读入 
26     bool flag=0;
27     char c;
28     while(scanf("%c",&c)){
29         if(c=='"')
30           if(flag==1)break;
31            else flag=1;
32         if(c>='0' && c<='9'){
33             n[++ct]=c-'0';
34         }
35     }
36     return;
37 }
38 void dfs(int cpls,int pos){//cpls-已用加号数量  pos-在第pos个数后插入 
39 //    printf("test  
");
40     if(cpls>mini)return;
41     int i,j;
42     int start=pos+1;
43     for(i=pos+1;i<=ct;i++){
44 //        printf("test message: s:%d  t:%d total:%d 
",start,i,ct);
45 //        printf("    sum:%d  + %d
",ansum,ssum(start,i));
46         ansum+=ssum(start,i);
47         if(ansum>m){        
48             ansum-=ssum(start,i);
49             break;}
50         if(ansum==m && i==ct){//只有i==ct时才算解 
51             mini=min(mini,cpls);
52             }
53         else
54             dfs(cpls+1,i);
55         ansum-=ssum(start,i);
56     }
57     return;
58 }
59 int main(){
60     read1();
61     cin>>m;
62     dfs(0,0);
63     cout<<mini;
64     return 0;    
65     
66 }

View Code

贪心式DFS：

保证总和不超过所求值m的情况下，每段截取得尽可能大，如此找到的第一个解就是最优解。

最差情况下基本等于暴搜，但平均看来效率还是比较高的

 1 /*Silver_N    quicksum*/
 2 #include<algorithm>
 3 #include<iostream>
 4 #include<cmath>
 5 #include<cstdio>
 6 using namespace std;
 7 int n[500];//每个数字 
 8 int re[200][200];
 9 int ct=0;//总字符数 
10 int mini=100000;//最小解 
11 int m;//需求数 
12 int ansum=0;
13 int flag=0;
14 int ssum(int s,int t){//截取 
15     int i,j;
16     if(re[s][t])return re[s][t];
17     //else begin
18     int x=0;
19     for(i=s;i<=t;i++){
20         x=x*10+n[i];
21     }
22     re[s][t]=x;
23     return x;
24     //end
25 }
26 void read1(){//读入 
27     bool flag=0;
28     char c;
29     while(scanf("%c",&c)){
30         if(c=='"')
31           if(flag==1)break;
32            else flag=1;
33         if(c>='0' && c<='9'){
34             n[++ct]=c-'0';
35         }
36     }
37     return;
38 }
39 void dfs(int cpls,int pos){//pos-在第pos个数后插入 
40 //    printf("test  
");
41     if(flag==1)return;
42     if(cpls>mini)return;
43     int i,j;
44     int start=pos+1;
45     for(i=ct;i>=pos+1;i--){//从后往前枚举位置，优先截取较长的串 
46 //        printf("test message: s:%d  t:%d total:%d 
",start,i,ct);
47 //        printf("    sum:%d  + %d
",ansum,ssum(start,i));
48         ansum+=ssum(start,i);
49         if(ansum>m){        
50             ansum-=ssum(start,i);
51             continue;}
52         if(ansum==m && i==ct){
53             mini=min(mini,cpls);
54             flag=1;//找到解的标志 
55             }
56         else
57             dfs(cpls+1,i);
58         if(flag==1)return;//找到一解直接退出 
59         ansum-=ssum(start,i);
60     }
61     return;
62 }
63 int main(){
64     read1();
65     cin>>m;
66     dfs(0,0);
67     if(mini==100000)cout<<"-1";
68     else cout<<mini;
69     return 0;
70     
71 }

View Code