首页 > 代码库 > HDU 5937 Equation（DFS+剪枝）
HDU 5937 Equation（DFS+剪枝）
题目链接 Equation
给定1-9这9个数字各自的卡片数，求能构成形如$i + j = k$的等式个数
等式中$i，j，k$必须都为个位数
若两个等式中$i，j，k$不完全相等，则这两个等式为不同的等式。
打表发现符合题意的等式有36个
那么通过01搜索状态数为$2^{36}$
TLE
我们求出若答案为36，每张卡片需求量$f[i]$
每次读入$a[i]$的时候
若对$i(1 <= i <= 9)$， 都有$a[i] >= f[i]$
则直接输出36
DFS的时候x为当前的等式用/不用
cnt为$1$到$x - 1$中用的等式个数
ans为当前保存答案的最大值
则当$cnt + 36 - x + 1 <= ans$的时候，剪枝
#include <bits/stdc++.h>using namespace std;#define rep(i, a, b) for (int i(a); i <= (b); ++i)#define dec(i, a, b) for (int i(a); i >= (b); --i)typedef long long LL;struct node{ int x, y, z;} c[105];int et = 0;int f[11];int a[11];int ans;int T;int ca = 0;vector <int> v;void dfs(int x, int cnt){ if (cnt + et - x + 1 <= ans) return; if (x > et){ ans = max(ans, cnt); return; } dfs(x + 1, cnt); --a[c[x].x]; --a[c[x].y]; --a[c[x].z]; if (a[c[x].x] >= 0 && a[c[x].y] >= 0 && a[c[x].z] >= 0){ dfs(x + 1, cnt + 1); ++a[c[x].x]; ++a[c[x].y]; ++a[c[x].z]; } else{ ++a[c[x].x]; ++a[c[x].y]; ++a[c[x].z]; } } int main(){ rep(i, 1, 9) rep(j, 1, 9) rep(k, 1, 9){ if (i + j == k){ ++et; c[et].x = i; c[et].y = j; c[et].z = k; ++f[i], ++f[j], ++f[k]; } } scanf("%d", &T); while (T--){ printf("Case #%d: ", ++ca); rep(i, 1, 9) scanf("%d", a + i); bool fl = true; rep(i, 1, 9) if (a[i] < f[i]){ fl = false; break; } if (fl){ printf("%d\n", et); continue; } ans = 0; dfs(1, 0); printf("%d\n", ans); } return 0;}
HDU 5937 Equation（DFS+剪枝）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。