參考題解：http://blog.csdn.net/lyy289065406/article/details/6647969 題意和思路在題解都有，思路很簡單，奈何我寫了好久愣是沒實現出來。。。
#include <iostream>#include <cmath>#include <cstring>using namespace std;int aim,result,path,sum,p;int vist[1000000];int Mpow(int a, int b){ int res = 1; while(b) { if(b & 1) res *= a; a = a*a; b >>= 1; } return res;}int getLen(int n){ return (int)log10(n)+1;}int getValue(char *s, int i){ int k = i; int sum = 0; int b,num,p; while(k) { k--; b = i-k-1; num = s[k] - '0'; p = num*Mpow(10,b); sum += p; } return sum;}int getHead(int n, int i){ int len = getLen(n); if(len <= i) return n; return n/Mpow(10,len-i);}int getTail(int n, int i){ return n%Mpow(10,i);}void DFS(char *s, int len){ if(len == 0) { vist[sum]++; if(sum > result && sum <= aim) { result = sum; path = p; } return; } for(int i = 1; i <= len; ++i) { int a = getValue(s,i); sum += a; if(sum > aim) { sum -= a; //continue; return; } p = p*10+i; char b[7]; int j = 0; for(int k = i; k < len; ++k) b[j++] = s[k]; b[j] = '/0'; DFS(b,len-i); sum -= a; p /= 10; } return;}int main(){ while(true) { char s[7]; cin >> aim >> s; int len = strlen(s); int n = getValue(s,len); if(!aim && !n) break; if(aim == n) { cout << aim << " " << n << endl; continue; } int num = n; int k = 0; while(num) { k += num%10; num /= 10; } if(k > aim) { cout << "error" << endl; continue; } result = -1; sum = 0; path = 0; p = 0; memset(vist,0,sizeof(vist)); DFS(s,len); if(vist[result] > 1) cout << "rejected" << endl; else if(vist[result] == 1) { cout << result << " "; int L = getLen(path); for(int i = 1; i <= L; ++i) { int k = getHead(path,1); cout << getHead(n,k) << " "; n = getTail(n,len-=k); path = getTail(path,L-i); } cout << endl; } } return 0;}新聞熱點
疑難解答
