[题解] 洛谷 P1120 小木棍 [数据加强版]

Problem:https://www.luogu.org/problemnew/show/P1120
这道搜索水题还是花了我蛮长时间的,主要在剪枝上。

具体看注释吧。

//P1120 木棍+木棍+······=木棒
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int INF=1e9+7;
int N;
int w[80],vis[80];
int MAX=-INF,ans=INF,sum=0,cnt=0,len=0; //len:原始木棒长度 cnt:根数
//bool flag=false;
inline bool dfs(int si,int siz,int res){  //si:当前拼的木棍编号   siz:当前拼好的长度   res:上一根小木棍
    if(si>cnt) return true;       //全拼完了(在Line 15调用si+1时),返回成功
    if(siz==len) return dfs(si+1,0,1);     //当前拼完了,去拼下一根
    int lastfail=0;            //记录上一根失败拼法(如果上一根长度相同的拼接搜索失败,就没必要继续搜索相同的长度了(见Line 18))
    for(register int i=res;i<=N;i++){
        if(!vis[i] && siz+w[i]<=len && w[i]!=lastfail){ //判断木棍是否用过/是否能拼够/Line 16 失败拼法
            vis[i]=true;  
            if(dfs(si,siz+w[i],i+1)) return true;  //如果能拼接搜索成功:返回
            //以下均为失败情况处理:回溯/记录:Line16失败情况
            lastfail=w[i];
            vis[i]=false;   //还原,以备下次使用
            if (siz==0 || siz+w[i]==len) return false;  //剪枝:如果失败情况下一点都未拼好/拼好了这种情况扔不成立,那么这层搜索不成立,返回失败。
        }
        
    }
    return false;
}



inline bool cmp(int a,int b){  //降序排列用
    return a>b;
}


int main(){
    scanf("%d",&N);   
    for(register int i=1;i<=N;i++){
        int t;scanf("%d",&t);
        if(t>50){   //自觉过滤大于50的情况
            i--,N--;
            continue;
        }else{
            w[i]=t;sum+=t;
            MAX=max(MAX,t);    //取最长木棍
        }
    }  //读入数据
    sort(w+1,w+1+N,cmp);     //降序排列
    for(len=MAX;len<=sum;len++){     //最短肯定是其中最长的木棍,最长肯定是木棍长度之和
    	//因为木棒等长,所以拼出来最短木棒长度一定能被木棍长度总长所整除(Line 54:整除出来的cnt为要拼木棒的根数)
        if((sum%len)) continue;    //等价于sum%len!=0 (C++非0为真)   
        cnt=sum/len;   //见Line 52
        memset(vis,0,sizeof(vis));  //初始化vis数组,防止重复选择
        if(dfs(1,0,1)) break;  //因为木棒选木棍是从大往小选(Line 50),且长度是从小到大枚举,所以第一次就能保证最优状态,直接剪枝跳出。

    }
    printf("%d",len);     //见Line 56
    return 0;
}
//By abc1763613206 2018.10.29

 




点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注

普人特福的博客cnzz&51la for wordpress,cnzz for wordpress,51la for wordpress