P1120 小木棍 ［数据加强版］ 回溯法 剪枝
---恢复内容开始---
题目描述
乔治有一些同样长的小木棍，他把这些木棍随意砍成几段，直到每段的长都不超过5050。
SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。现在，他想把小木棍拼接成原来的样子，但是却忘记了自己开始时有多少根木棍和它们的长度。
给出每段小木棍的长度，编程帮他找出原始木棍的最小可能长度。
输入输出格式
输入格式：
共二行。
第一行为一个单独的整数N表示砍过以后的小木棍的总数，其中N≤65N≤65
（管理员注：要把超过5050的长度自觉过滤掉，坑了很多人了！）
第二行为NN个用空个隔开的正整数，表示NN根小木棍的长度。
输出格式：
一个数，表示要求的原始木棍的最小可能长度
输入输出样例
输入样例#1： 复制9 5 2 1 5 2 1 5 2 1输出样例#1： 复制
6
说明
2017/08/05
数据时限修改：
-#17 #20 #22 #27 四组数据时限500ms500ms
-#21 #24 #28 #29 #30五组数据时限1000ms1000ms
其他时限改为200ms200ms（请放心食用）
一开始想贪心什么的 肯定是暴力搜索 只管搜就完事了
dfs回溯法
小优化: 27分
#include<bits/stdc++.h> using namespace std; //input by bxd #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define repp(i,a,b) for(int i=(a);i>=(b);i--) #define RI(n) scanf("%d",&(n)) #define RII(n,m) scanf("%d%d",&n,&m) #define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k) #define RS(s) scanf("%s",s); #define ll long long #define REP(i,N) for(int i=0;i<(N);i++) #define CLR(A,v) memset(A,v,sizeof A) ////////////////////////////////// #define inf 214748347 #define N 1500+5 int cnt=0; int sum=0; int n; int a[100]; int vis[100]; int minn; int ok; void dfs(int tot,int t) { if(ok)return ; if(t==0) { ok=1; printf("%d\n",minn); } rep(i,1,cnt) if(!vis[i]) { if(tot+a[i]<minn) { vis[i]=1; dfs(tot+a[i],t); vis[i]=0; } else if(tot+a[i]==minn) { vis[i]=1; dfs(0,t-1); vis[i]=0; } } } int main() { int n; RI(n); rep(i,1,n) { int x; RI(x); if(x<=50) { sum+=x; a[++cnt]=x; } } sort(a+1,a+1+cnt); for(minn=a[cnt];;minn++) { if(sum%minn)continue;//剪枝 n=sum/minn; CLR(vis,0); ok=0; dfs(0,n); if(ok)break; } return 0; }View Code
二分找最后一个点优化：33分
#include<bits/stdc++.h> using namespace std; //input by bxd #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define repp(i,a,b) for(int i=(a);i>=(b);i--) #define RI(n) scanf("%d",&(n)) #define RII(n,m) scanf("%d%d",&n,&m) #define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k) #define RS(s) scanf("%s",s); #define ll long long #define REP(i,N) for(int i=0;i<(N);i++) #define CLR(A,v) memset(A,v,sizeof A) ////////////////////////////////// #define inf 214748347 #define N 1500+5 int cnt=0; int sum=0; int n; int a[100]; int vis[100]; int minn; int ok; void dfs(int tot,int t) { if(ok)return ; if(t==0) { ok=1; printf("%d\n",minn); } rep(i,1,cnt) if(!vis[i]) { if(tot+a[i]==minn) { vis[i]=1; dfs(0,t-1); vis[i]=0; } else if(tot+a[i]<minn) { int b=tot+a[i]; int pos=lower_bound(a+1,a+1+cnt,minn-b)-a; while( a[pos]==minn-b&&vis[pos])pos++; if(a[pos]==minn-b) { vis[i]=1; vis[pos]=1; dfs(0,t-1); vis[i]=0; vis[pos]=0; } else { vis[i]=1; dfs(tot+a[i],t); vis[i]=0; } } } } int main() { int n; RI(n); rep(i,1,n) { int x; RI(x); if(x<=50) { sum+=x; a[++cnt]=x; } } sort(a+1,a+1+cnt); for(minn=a[cnt];;minn++) { if(sum%minn)continue; n=sum/minn; CLR(vis,0); ok=0; dfs(0,n); if(ok)break; } return 0; }View Code
事实证明这个二分没什么用
将大的放在前面更好！！！！！
加一个排序就33了
#include<bits/stdc++.h> using namespace std; //input by bxd #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define repp(i,a,b) for(int i=(a);i>=(b);i--) #define RI(n) scanf("%d",&(n)) #define RII(n,m) scanf("%d%d",&n,&m) #define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k) #define RS(s) scanf("%s",s); #define ll long long #define REP(i,N) for(int i=0;i<(N);i++) #define CLR(A,v) memset(A,v,sizeof A) ////////////////////////////////// #define inf 214748347 #define N 1500+5 int cnt=0; int sum=0; int n; int a[100]; int vis[100]; int minn; int ok; bool cmp(int a,int b) { return a>b; } void dfs(int tot,int t) { if(ok)return ; if(t==0) { ok=1; printf("%d\n",minn); } rep(i,1,cnt) if(!vis[i]) { if(tot+a[i]==minn) { vis[i]=1; dfs(0,t-1); vis[i]=0; } else if(tot+a[i]<minn) { vis[i]=1; dfs(tot+a[i],t); vis[i]=0; } } } int main() { int n; RI(n); rep(i,1,n) { int x; RI(x); if(x<=50) { sum+=x; a[++cnt]=x; } } sort(a+1,a+1+cnt,cmp); for(minn=a[1];;minn++) { if(sum%minn)continue; n=sum/minn; CLR(vis,0); ok=0; dfs(0,n); if(ok)break; } return 0; }View Code
再对 匹配完成进行小优化? 51分 //帮助头匹配很重要
#include<bits/stdc++.h> using namespace std; //input by bxd #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define repp(i,a,b) for(int i=(a);i>=(b);i--) #define RI(n) scanf("%d",&(n)) #define RII(n,m) scanf("%d%d",&n,&m) #define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k) #define RS(s) scanf("%s",s); #define ll long long #define REP(i,N) for(int i=0;i<(N);i++) #define CLR(A,v) memset(A,v,sizeof A) ////////////////////////////////// #define inf 214748347 #define N 1500+5 int cnt=0; int sum=0; int n; int a[100]; int vis[100]; int minn; int ok; bool cmp(int a,int b) { return a>b; } void dfs(int tot,int t,int cur) { if(ok)return ; if(t==0) { ok=1; printf("%d\n",minn); } int d=minn-tot; int L=cur; int R=cnt; rep(i,1,cnt) { if(vis[i])continue; if(tot+a[i]==minn) { vis[i]=1; int j; for( j=1;j<=cnt;j++) if(!vis[j])break; vis[j]=1; dfs(a[j],t-1,i); vis[j]=0; vis[i]=0; } if(tot+a[i]<minn) { vis[i]=1; dfs(tot+a[i],t,i); vis[i]=0; } } } int main() { int n; RI(n); rep(i,1,n) { int x; RI(x); if(x<=50) { sum+=x; a[++cnt]=x; } } sort(a+1,a+1+cnt,cmp); for(minn=a[1];;minn++) { if(sum%minn)continue; n=sum/minn; CLR(vis,0); ok=0; dfs(0,n,1); if(ok)break; } return 0; }View Code
二分优化： 60
#include<bits/stdc++.h> using namespace std; //input by bxd #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define repp(i,a,b) for(int i=(a);i>=(b);i--) #define RI(n) scanf("%d",&(n)) #define RII(n,m) scanf("%d%d",&n,&m) #define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k) #define RS(s) scanf("%s",s); #define ll long long #define REP(i,N) for(int i=0;i<(N);i++) #define CLR(A,v) memset(A,v,sizeof A) ////////////////////////////////// #define inf 214748347 #define N 1500+5 int cnt=0; int sum=0; int n; int a[100]; int vis[100]; int minn; int ok; bool cmp(int a,int b) { return a>b; } void dfs(int tot,int t,int cur) { if(ok)return ; if(tot==minn) { t--; if(t==0) { ok=1;return; } int i; for( i=1;i<=cnt;i++) if(!vis[i])break; vis[i]=1; dfs(a[i],t,i); vis[i]=0; if(ok)return; } int L=cur; int R=cnt; while(L<R) { int mid=(L+R)>>1; if(a[mid]>minn-tot)L=mid+1; else R=mid; } for(int i=L;i<=cnt;i++) { if(vis[i])continue; if(tot+a[i]<=minn) { vis[i]=1; dfs(tot+a[i],t,i); vis[i]=0; } } } int main() { int n; RI(n); rep(i,1,n) { int x; RI(x); if(x<=50) { sum+=x; a[++cnt]=x; } } sort(a+1,a+1+cnt,cmp); for(minn=a[1];;minn++) { if(sum%minn)continue; n=sum/minn; CLR(vis,0); ok=0; vis[1]=1; dfs(a[1],n,1); vis[1]=0; if(ok) { printf("%d\n",minn);break; } } return 0; }View Code
更多精彩
