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