状压dp的典型的例子就是其中某个数值较小。
但是某个数值较小也不一定是状压dp，需要另外区分的一种题目就是用暴力解决的题目，例如UVA818 紫书215
题目列表：
①校长的烦恼 UVA10817 紫书286
②20个问题 UVA 1252 紫书287
③
④
⑤
⑥
⑦
⑧
⑨
⑩
一：校长的烦恼 UVA10817 紫书286
题目大意：n个求职者，m个教师，需要讲授s门课程，每门课要有至少2个人讲授。教师是必须雇佣的，求职者看情况。给出教师和求职者的工资和能教授的科目。问怎么雇佣才能支付最少的工资？
思路：定义dp[i][s1][s2]表示，s1表示每门课只有一个人教，s2表示每门课有两名以上的人教的。i表示前i个人的雇佣情况，这样进行dp就好了。 具体看紫书吧，很详细
//看看会不会爆int! 或者绝对值问题。
#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define pb push_back
#define mk make_pair
#define fi first
#define se second
#define ALL(a) a.begin(), a.end()
const int maxs = ( << ) + ;
const int inf = 0x3f3f3f3f;
const int maxn = + ;
int s, m, n;
int dp[maxn][maxs][maxs], money[maxn], st[maxn]; int dfs(int i, int s1, int s2){
if (i == m + n){
return s2 == (<<s)- ? : inf;
}
int &ans = dp[i][s1][s2];
if (ans >= ) return ans;
ans = inf;
if (i >= m) ans = dfs(i + , s1, s2);
int t = st[i];
int tmp = s1 & t;
ans = min(ans, dfs(i + , s1 | t, s2 | tmp) + money[i]);
return ans;
} int main(){
string line;
int x;
while (getline(cin, line)){
stringstream ss(line);
ss >> s >> m >> n;
if (s == ) break;
for (int i = ; i < m + n; i++){
getline(cin, line);
stringstream ss(line);
ss >> money[i];
st[i] = ;
while (ss >> x) st[i] |= ( << x-);
}
memset(dp, -, sizeof(dp));
dfs(, , );
printf("%d\n", dp[][][]);
}
return ;
}
关键：学会划分情况
二：20个问题 UVA1252 紫书267
题目大意：有n个长度为m的二进制串，每个都是不同的。为了把所有字符串区分开，你可以询问，每次可以问某位上是0还是1。问最少提问次数，可以把所有字符串区分开来。
思路：dp是要枚举已知的所需要的所有状态的，那么我们如何来枚举目前的状态呢。首先我们定义dp[s][a],s表示目前已经询问了的集合，a表示目前s的子集当中的特征集。因此就表示，已经询问了特征集s，确认了所具备的特征集a，还需要询问的最小次数是多少。
因此我们的决策时dp[s][a] = max(dp[s + {k}][a + {k}], dp[s + {k}][a]) + 1;
然后通过dfs来解决就行了。虽然也可以用递推来实现。
//看看会不会爆int! 或者绝对值问题。
#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define pb push_back
#define mk make_pair
#define fi first
#define se second
#define ALL(a) a.begin(), a.end()
///当所有的物品所具备的特征只剩下1的时候，说明其他全都访问过
const int maxn = + ;
const int maxm = ( << ) + ;
int cnt[maxm][maxm], dp[maxm][maxm];
int n, m;
char ch[maxn]; void init(){
memset(cnt, , sizeof(cnt));
for (int i = ; i < n; i++){
scanf("%s", ch);
int t = ;
for (int j = ; j < m; j++)
if (ch[j] == '') t |= ( << j);
for (int j = ; j < ( << m); j++){///给所有的都做上标记,一个的时候，两个的时候都有
cnt[j][j & t]++;
}
}
} int dfs(int s, int a){
if (cnt[s][a] <= ) return ;
if (cnt[s][a] == ) return ; int &ans = dp[s][a];
if (dp[s][a] >= ) return ans;
ans = m;
for (int i = ; i < m; i++){
if (s & ( << i)) continue;
int s2 = s | ( << i), a2 = a | ( << i);
if (cnt[s2][a] >= && cnt[s2][a2] >= ){
int tmp = max(dfs(s2, a), dfs(s2, a2)) + ;
ans = min(tmp, ans);
}
}
return ans;
} int main(){
while (scanf("%d%d", &m, &n) == && n+m > ){
memset(dp, -, sizeof(dp));
init();
printf("%d\n", dfs(, ));
}
return ;
}
感觉这道题让现在我这样的水平的人来做肯定做不来，要仔细看看
三：
四：
五：
六：
七：
八：
九：
十：