22/5/21

1，dfs剪枝：eg1：acwing 167.木棒；eg2：acwing 168.生日蛋糕；

---

1，dfs剪枝：

剪枝策略有四种，

优化搜索顺序（多理解也要多想到），

排除等效冗余（尽量不搜重复的），

可行性剪枝；

最优性剪枝；

eg1：木棒；

题意：

 要正确理解题意，实质是本题是找最小的组和同时使得各个组里的木棍的和相等；

思路：枚举。把大木棍长从1开始枚举，然后再用给的小木棍长去拼凑大木棍长，如果能拼出来，说明这就是一合法解，且因为从小到大枚举，所以也是最小的大木棍长；

剪枝方式：

①：可行性剪枝：只有当sum（所有小木棍的和）%大木棍的len==0时，才可以去拼凑；

②：优化搜索顺序，优先用大的拼，这样会及时找到不满足的情况从而return（这种技巧还挺常用的）；

③：排除等效冗余：按组合顺序拼，所以可行的方式是按下标枚举小木棍的长度，然后用st[]数组标记用没用过；

④：本题特有的剪枝：当枚举的第一个小木棍长和最后一个小木棍长不符合时，直接return；

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define rep1(i,a,n) for(register int i=a;i<n;++i) 
#define rep2(i,a,n) for(register int i=a;i<=n;++i) 
#define per1(i,n,a) for(register int i=n;i>a;i--) 
#define per2(i,n,a) for(register int i=n;i>=a;i--)
#define quick_cin() cin.tie(0),cout.tie(0),ios::sync_with_stdio(false)
#define memset(a,i) memset((a),(i),sizeof (a))
#define memcpy(a,i) memcpy((a),(i),sizeof (a))
#define pro_q priority_queue
#define pb push_back
#define pf push_front
#define endl "\n"
#define lowbit(m) ((-m)&(m))
#define YES cout<<"YES\n"
#define NO cout<<"NO\n"
#define Yes cout<<"Yes\n"
#define No cout<<"No\n"
#define yes cout<<"yes\n"
#define no cout<<"no\n"
#define yi first
#define er second
using namespace std;
typedef pair<int,int> PII;
typedef pair<long long,long long>PLL;
typedef pair<int,PII> PIII;
typedef long long ll;
typedef double dob;
const int N=70;
int n;
int w[N];
int sum,len;
int st[N];
bool dfs(int u,int cur,int start)
{
    if(u*len==sum)return 1;
    if(cur==len)return dfs(u+1,0,0);
    rep1(i,start,n)
    {
        if(st[i]||cur+w[i]>len)continue;
        st[i]=1;
        if(dfs(u,cur+w[i],i+1))return 1;
        st[i]=0;
        if(!cur||cur+w[i]==len)return 0;
        int j=i;
        while(j<n&&w[j]==w[i])j++;
        i=j-1;
    }
    return 0;
}
signed main()
{
    quick_cin();
    while(cin>>n,n)
    {
        memset(st,0);
        sum=0;
        rep1(i,0,n)cin>>w[i],sum+=w[i];
        sort(w,w+n,greater<int>());
        len=1;
        while(1)
        {
            if(sum%len==0&&dfs(0,0,0))
            {
                cout<<len<<endl;
                break;
            }
            len++;
        }
    }
    return 0;
}

eg2：生日蛋糕；

题意：
 思路：枚举r和h；

优化：
优化搜索顺序：①从下层到上层枚举；②：先枚举半径再枚举高；

可行性剪枝：数学推导，（来自acwing random_srand ）；

 

 数学推导挺难想的，重在积累吧；

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define rep1(i,a,n) for(register int i=a;i<n;++i) 
#define rep2(i,a,n) for(register int i=a;i<=n;++i) 
#define per1(i,n,a) for(register int i=n;i>a;i--) 
#define per2(i,n,a) for(register int i=n;i>=a;i--)
#define quick_cin() cin.tie(0),cout.tie(0),ios::sync_with_stdio(false)
#define memset(a,i) memset((a),(i),sizeof (a))
#define memcpy(a,i) memcpy((a),(i),sizeof (a))
#define pro_q priority_queue
#define pb push_back
#define pf push_front
#define endl "\n"
#define lowbit(m) ((-m)&(m))
#define YES cout<<"YES\n"
#define NO cout<<"NO\n"
#define Yes cout<<"Yes\n"
#define No cout<<"No\n"
#define yes cout<<"yes\n"
#define no cout<<"no\n"
#define yi first
#define er second
using namespace std;
typedef pair<int,int> PII;
typedef pair<long long,long long>PLL;
typedef pair<int,PII> PIII;
typedef long long ll;
typedef double dob;
const int N=25,inf=1e9;
int n,m;
int minv[N],mins[N];
int R[N],H[N];
int ans=inf;
void dfs(int u,int v,int s)
{
    if(v+minv[u]>n)return;
    if(s+mins[u]>=ans)return;
    if(s+2*(n-v)/R[u+1]>=ans)return;
    if(!u)
    {
        if(v==n)ans=s;
        return;
    }
    for(int r=min(R[u+1]-1,(int)sqrt(n-v));r>=u;r--)
    {
        for(int h=min(H[u+1]-1,(n-v)/r/r);h>=u;h--)
        {
            int t=0;
            if(u==m)t=r*r;
            R[u]=r,H[u]=h;
            dfs(u-1,v+r*r*h,s+2*r*h+t);
        }
    }
}
signed main()
{
    quick_cin();
    cin>>n>>m;
    rep2(i,1,m)
    {
        minv[i]=minv[i-1]+i*i*i;
        mins[i]=mins[i-1]+2*i*i;
    }
    R[m+1]=H[m+1]=inf;
    dfs(m,0,0);
    if(ans==inf)ans=0;
    cout<<ans<<endl;
 
    return 0;
}