dfs专题

acwing165
深搜就完了，深搜的时候有两个状态，一个是当前装的是第now只小猫（前now-1只小猫装完），一个是cnt，表示租用了的缆车的数量.
优化：如果在搜索的时候发现cnt大于等于答案ans就结束,且装小猫的时候先装大的猫，减少分支

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const ll mod = 1e9 + 7;
const ll N = 5e2 + 7;
const ll maxn = 1e5 + 7, maxm = 2e5 + 7;
inline ll read()
{
    ll s = 0, w = 1;
    char ch = getchar();
    while (ch < 48 || ch > 57)
    {
        if (ch == '-')
            w = -1;
        ch = getchar();
    }
    while (ch >= 48 && ch <= 57)
        s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}
inline void write(ll m)
{
    if (!m)
    {
        putchar('0');
        return;
    }
    char F[200];
    ll tmp = m > 0 ? m : -m;
    if (m < 0)
        putchar('-');
    int cnt = 0;
    while (tmp > 0)
    {
        F[cnt++] = tmp % 10 + '0';
        tmp /= 10;
    }
    while (cnt > 0)
        putchar(F[--cnt]);
}
ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll x, ll y, ll mod)
{
    ll ans = 1;
    while (y)
    {
        if (y & 1)
            (ans *= x) %= mod;
        y >>= 1;
        (x *= x) %= mod;
    }
    return ans % mod;
}
int cab[N] , a[N] ,n,w,ans;
bool cmp(int a,int b){
    return a > b;
}
void dfs(int now , int cnt){
    if(cnt >= ans) return;
    if(now == n+1){
        ans = min(ans,cnt);
        return;
    }
    for(int i = 1 ; i <= cnt ; i++){
        if(cab[i] + a[now] <= w){
            cab[i] += a[now];
            dfs(now + 1, cnt);
            cab[i] -= a[now];
        }
    }
    cab[cnt + 1] += a[now];
    dfs(now + 1, cnt+1);
    cab[cnt + 1] -= a[now]; 
}
int main()
{
    n = read() , w = read();
    ans = n;
    for(int i = 1; i <= n ; i++) a[i] = read();
    sort(a + 1 , a + 1 + n, cmp);
    dfs(1,0);
    cout<<ans<<endl;
}

acwing167

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const ll mod = 1e9 + 7;
const ll N = 5e2 + 7;
const ll maxn = 1e5 + 7, maxm = 2e5 + 7;
inline ll read()
{
    ll s = 0, w = 1;
    char ch = getchar();
    while (ch < 48 || ch > 57)
    {
        if (ch == '-')
            w = -1;
        ch = getchar();
    }
    while (ch >= 48 && ch <= 57)
        s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}
inline void write(ll m)
{
    if (!m)
    {
        putchar('0');
        return;
    }
    char F[200];
    ll tmp = m > 0 ? m : -m;
    if (m < 0)
        putchar('-');
    int cnt = 0;
    while (tmp > 0)
    {
        F[cnt++] = tmp % 10 + '0';
        tmp /= 10;
    }
    while (cnt > 0)
        putchar(F[--cnt]);
}
ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll x, ll y, ll mod)
{
    ll ans = 1;
    while (y)
    {
        if (y & 1)
            (ans *= x) %= mod;
        y >>= 1;
        (x *= x) %= mod;
    }
    return ans % mod;
}
int cab[N], a[N] ,n, ans , len , sum , cnt;
bool cmp(int a,int b){
    return a > b;
}
bool vis[N];
bool dfs(int stick ,int cab ,int last){
    //cab当前木棒拼接的长度
    //stick当前拼的是第几根木棒
    if(stick == cnt) return true;
    if(cab == len) return dfs(stick + 1 , 0 , 1);
    int fail = 0;
    for(int i = last ; i <= n ; i++){
        if(!vis[i] && cab + a[i] <= len && fail != a[i]){
            vis[i] = 1;
            if(dfs(stick , cab + a[i] , last + 1)) return true;
            fail = a[i];//去除无效的长度
            vis[i] = 0;
            if(cab == 0 || cab + a[i] == len) return false;
            //拼这个木棒的递归分支失败，其他的也失败
            //拼当前木棒的递归分支失败，其他的也必定失败，因为即使用其他的木棒凑这个木棒也是一样的
        }
    }
    return false;
}
int main()
{
   while(cin>>n && n != 0){
       sum = 0;
       for(int i = 1; i <= n ; i++) a[i] = read(), sum += a[i];
       sort(a + 1 , a + 1 + n, cmp);
       for(len = a[1] ; len <= sum ; len++){
           if(sum % len != 0) continue;
           cnt = sum / len;
           memset(vis, 0 , sizeof(vis));
           if(dfs(0,0,1)) break;
       }
       cout<<len<<endl;
   }
}

acwing170
题解：迭代搜索，限制搜索的深度

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const ll mod = 1e9 + 7;
const ll N = 5e2 + 7;
const ll maxn = 1e5 + 7, maxm = 2e5 + 7;
inline ll read()
{
    ll s = 0, w = 1;
    char ch = getchar();
    while (ch < 48 || ch > 57)
    {
        if (ch == '-')
            w = -1;
        ch = getchar();
    }
    while (ch >= 48 && ch <= 57)
        s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}
inline void write(ll m)
{
    if (!m)
    {
        putchar('0');
        return;
    }
    char F[200];
    ll tmp = m > 0 ? m : -m;
    if (m < 0)
        putchar('-');
    int cnt = 0;
    while (tmp > 0)
    {
        F[cnt++] = tmp % 10 + '0';
        tmp /= 10;
    }
    while (cnt > 0)
        putchar(F[--cnt]);
}
ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll x, ll y, ll mod)
{
    ll ans = 1;
    while (y)
    {
        if (y & 1)
            (ans *= x) %= mod;
        y >>= 1;
        (x *= x) %= mod;
    }
    return ans % mod;
}
int x[N] ,n, ans , vis[N];
bool cmp(int a,int b){
    return a > b;
}
bool dfs(int d ,int maxd){
    if(d == maxd)  return x[d - 1] == n;
    memset(vis, 0 ,sizeof(vis));
    for(int i = d-1 ; i >= 0 ; i--){
        for(int j = i ;j >= 0 ; j--){
            int s = x[i] + x[j];
            if(vis[s] || s > n || s <= x[d-1]) continue;
            vis[s] = 1;
            x[d] = s;
            if(dfs(d + 1, maxd)) return true; 
        }
    }
    return false;
}
int main()
{
   x[0] = 1;
   while(cin>>n && n != 0){
       int maxd = 1;
       while(!dfs(1,maxd))   maxd++;
       for(int i = 0 ; i < maxd ; i++) printf("%d ", x[i]);
       printf("\n");
   }
}