首页 > 代码库 > POJ 1416-Shredding Company(DFS+更新路径)
POJ 1416-Shredding Company(DFS+更新路径)
题目链接:传送门
题意:给一个目标值goal,然后再给一个数num,将num分解,比如 给目标值50,num为12346 num可以分解为 1 2 34 6 这么4部分,要求部分和尽量接近目标值但不能大于目标值,求最优分解;
思路:深搜每次分割部分的起点,更新最优解的时候更新一下路径,以前也是被路径打印给困惑了,其实和更新最优值思想一样,可以设一个ans_path[] 数组,更新最优值的时候顺便更新一下最优路径就行了。。
#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')*(int)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; }
POJ 1416-Shredding Company(DFS+更新路径)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。