首页 > 代码库 > [dfs] UVALive 3667 Ruler
[dfs] UVALive 3667 Ruler
题目链接:
option=com_onlinejudge&Itemid=8&page=show_problem&problem=1668">https://icpcarchive.ecs.baylor.edu/index.php?
option=com_onlinejudge&Itemid=8&page=show_problem&problem=1668
option=com_onlinejudge&Itemid=8&category=0" style="color:rgb(33,93,198)">Root | option=com_onlinejudge&Itemid=8&page=submit_problem&problemid=1668&category=" style="color:rgb(33,93,198)"> |
Regionals 2006 >> option=com_onlinejudge&Itemid=8&category=242" style="color:rgb(33,93,198)">Asia - Beijing 3667 - RulerTime limit: 3.000 seconds |
题目意思:
有n个长度须要量。问如何设计尺子刻度,使得每一个长度都在两个刻度之间。在满足刻度数最小的情况下。要求尺子长度越短越好,最開始的刻度为0.
解题思路:
dfs
由于最多的刻度是7,并且可以计算出最小的刻度数。由于当刻度数m确定后。最多可以測量的长度数是固定的C(m,2).
要满足刻度最少且长度最短,能够如果最后一个刻度在长度最长的位置。
然后递增暴搜。
代码:
//#include<CSpreadSheet.h> #include<iostream> #include<cmath> #include<cstdio> #include<sstream> #include<cstdlib> #include<string> #include<string.h> #include<cstring> #include<algorithm> #include<vector> #include<map> #include<set> #include<stack> #include<list> #include<queue> #include<ctime> #include<bitset> #include<cmath> #define eps 1e-6 #define INF 0x3f3f3f3f #define PI acos(-1.0) #define ll __int64 #define LL long long #define lson l,m,(rt<<1) #define rson m+1,r,(rt<<1)|1 #define M 1000000007 //#pragma comment(linker, "/STACK:1024000000,1024000000") using namespace std; #define Maxn 55 #define Maxm 1100000 int hav[Maxm],sa[Maxn],n,ans; bool vis[Maxn]; int dis[Maxn]; bool dfs(int cur) { if(cur==ans) { for(int i=1;i<n;i++) //前n-1个长度都可以測量 if(!vis[i]) return false; return true; } for(int i=1;i<cur;i++) { for(int j=1;j<n;j++) { if(!vis[j]) { int dd=dis[i]+sa[j];//当前刻度 if(dd<=dis[cur-1]) //比之前大 continue; if(dd>=sa[n])//要比最大小 continue; dis[cur]=dd; queue<int>myq; //记录标记的长度。回溯时返回 for(int k=1;k<cur;k++) //增加当前刻度后,新增的可以出的长度 { int temp=dis[cur]-dis[k]; if(hav[temp]&&!vis[hav[temp]]) { vis[hav[temp]]=true; myq.push(hav[temp]); } } int la=sa[n]-dis[cur]; //最后一段 if(hav[la]&&!vis[hav[la]]) { vis[hav[la]]=true; myq.push(hav[la]); } if(dfs(cur+1)) return true; while(!myq.empty()) { la=myq.front(); myq.pop(); vis[la]=false; } } } } return false; } int main() { //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); int cas=0; while(~scanf("%d",&n)&&n) { for(int i=1;i<=n;i++) scanf("%d",&sa[i]); sort(sa+1,sa+n+1); n=unique(sa+1,sa+n+1)-sa-1; memset(hav,0,sizeof(hav)); for(int i=1;i<=n;i++) hav[sa[i]]=i; dis[1]=0; ans=2; while(ans*(ans-1)/2<n) ans++; memset(vis,0,sizeof(vis)); while(!dfs(2)) ans++; printf("Case %d:\n%d\n",++cas,ans); printf("%d",dis[1]); dis[ans]=sa[n]; for(int i=2;i<=ans;i++) printf(" %d",dis[i]); putchar('\n'); } return 0; }
[dfs] UVALive 3667 Ruler
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。