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; }
#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"); } }
搜索 文章被收录于专栏
刷题刷题