Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
一开始不知道怎么输出路径在更新最优解的时候用另外一个数组更新路径就好了。。 代码很挫。。sad #include <algorithm> #include <iostream> #include <cstring> #include <cstdlib> #include <string> #include <cctype> #include <vector> #include <cstdio> #include <cmath> #include <queue> #include<time.h> #include <stack> #include <map> #include <set> #define maxn 360 #define _ll __int64 #define ll long long #define INF 0x3f3f3f3f #define Mod 1000000007 #define pp pair<int,int> #define ull unsigned long long #define max(x,y) ( ((x) > (y)) ? (x) : (y) ) #define min(x,y) ( ((x) > (y)) ? (y) : (x) ) using namespace std; char s[100]; int ok,ans,path[20],ans_path[20],len,goal,rej,ans_tot; int my_pow(int a,int n) { int p=1; for(int i=1;i<=n;i++) p*=a; return p; } void dfs(int num,int sum,int tot) { if(sum>goal)return ; if(num>=len) { if(sum>ans&&sum<=goal) { memcpy(ans_path,path,sizeof(int)*tot); ok=1;rej=1;ans=sum;ans_tot=tot; return ; } else if(sum==ans&&sum<=goal) { rej++; return ; } return ; } for(int i=1;num+i<=len;i++) { int j=num+i,tem=0,sb=0; while(j>num)tem+=(s[j--]-'0')*my_pow(10,sb++); path[tot]=num+i; dfs(num+i,sum+tem,tot+1); path[tot]=-1; } } void print() { if(rej>1) { puts("rejected"); return ; } if(ok) { printf("%d",ans); for(int i=0;i<ans_tot;i++) { printf(" "); for(int j=(i!=0?ans_path[i-1]+1:1);j<=ans_path[i];j++) printf("%c",s[j]); } puts(""); } else puts("error"); } int main() { while(scanf("%d%s",&goal,s+1)&&(goal!=0&&s[1]!='0')) { memset(path,-1,sizeof(path)); s[0]=2;len=strlen(s)-1; ans=-INF;ok=0;rej=0;dfs(0,0,0); print(); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator