[UVA][bitmask、DP] 1252 - Twenty Questions
Consider a closed world and a set of features that are defined for all the objects in the world. Each feature can be answered with ``yes" or ``no". Using those features, we can identify any object from the rest of the objects in the world. In other words, each object can be represented as a fixed-length sequence of booleans. Any object is different from other objects by at least one feature.
You would like to identify an object from others. For this purpose, you can ask a series of questions to someone who knows what the object is. Every question you can ask is about one of the features. He/she immediately answers each question with ``yes" or ``no" correctly. You can choose the next question after you get the answer to the previous question.
You kindly pay the answerer 100 yen as a tip for each question. Because you don't have surplus money, it is necessary to minimize the number of questions in the worst case. You don't know what is the correct answer, but fortunately know all the objects in the world. Therefore, you can plan an optimal strategy before you start questioning.
The problem you have to solve is: given a set of boolean-encoded objects, minimize the maximum number of questions by which every object in the set is identifiable.
Input
The input is a sequence of multiple datasets. Each dataset begins with a line which
consists of two integers, m and n: the number of features, and the number of objects,
respectively. You can assume
0 < m
11 and
0 < n128. It is followed by
n lines, each of which corresponds to an object. Each line includes a binary string
of length m which represent the value (``yes" or ``no") of features. There are no two
identical objects.
The end of the input is indicated by a line containing two zeros. There are at most 100 datasets.
Output
For each dataset, minimize the maximum number of questions by which every object is identifiable and output the result.
Sample Input
8 1 11010101 11 4 00111001100 01001101011 01010000011 01100110001 11 16 01000101111 01011000000 01011111001 01101101001 01110010111 01110100111 10000001010 10010001000 10010110100 10100010100 10101010110 10110100010 11001010011 11011001001 11111000111 11111011101 11 12 10000000000 01000000000 00100000000 00010000000 00001000000 00000100000 00000010000 00000001000 00000000100 00000000010 00000000001 00000000000 9 32 001000000 000100000 000010000 000001000 000000100 000000010 000000001 000000000 011000000 010100000 010010000 010001000 010000100 010000010 010000001 010000000 101000000 100100000 100010000 100001000 100000100 100000010 100000001 100000000 111000000 110100000 110010000 110001000 110000100 110000010 110000001 110000000 0 0
Sample Output
0 2 4 11 9
題目描述：
有很多物件，然後都具有共同屬性，而屬性只有 yes or no，接著要求規劃詢問屬性的順序，
使之可以在任一個物件詢問答次數的最大值最小化。
將狀態壓縮一下，把詢問過的屬性進行壓縮，同時也將剩餘的問題分成 yes or no 兩堆。
因此當對於問題 i 發問時，根據當前剩餘的問題進行分兩堆
因此 ans = min(ans, max(yes_state, no_state)+1);
再次聲明狀態 [使用過的題目][剩餘的問題]
由於剩餘的問題 128 題, 可以用兩個 unsigned long long 去填裝, 因此進行壓縮，
用 lowbit 去抓取 // x&-x 仍是可以在 unsigned long long 中找到最後一位
//0.332 ms, rank 14
#include <stdio.h>
#include <map>
using namespace std;
struct ELE {
int probUsed, objItem;
unsigned long long obj1, obj2;
ELE(int a, int b, unsigned long long c, unsigned long long d):
probUsed(a),objItem(b),obj1(c), obj2(d){}
bool operator<(const ELE &a) const {
if(obj1 != a.obj1)
return obj1 < a.obj1;
if(probUsed != a.probUsed)
return probUsed < a.probUsed;
return obj2 < a.obj2;
}
};
int obj[128], n, m;
map<ELE, int> dp[1<<11];
//map<unsigned long long, int> low2bit;
int low2bit[1008];
int dfs(ELE &node) {
if(node.objItem <= 1)
return 0;
if(dp[node.probUsed].find(node) != dp[node.probUsed].end())
return dp[node.probUsed][node];
int &res = dp[node.probUsed][node];
int i, j, left, right;
res = 0xffff;
for(i = 0; i < n; i++) {
if(!((node.probUsed>>i)&1)) {
ELE yes(node.probUsed|(1<<i),0,0,0);
ELE no(node.probUsed|(1<<i),0,0,0);
unsigned long long x = node.obj1, v;
while(x) {
v = x&-x;
j = low2bit[v%1007];
if((obj[j]>>i)&1) {
yes.objItem++;
yes.obj1 |= 1ULL<<j;
} else {
no.objItem++;
no.obj1 |= 1ULL<<j;
}
x ^= v;
}
x = node.obj2;
while(x) {
v = x&-x;
j = low2bit[v%1007];
if((obj[j+64]>>i)&1) {
yes.objItem++;
yes.obj2 |= 1ULL<<j;
} else {
no.objItem++;
no.obj2 |= 1ULL<<j;
}
x ^= v;
}
left = dfs(yes);
if(left+1 >= res)
continue;
right = dfs(no);
res = min(res, max(dfs(yes),dfs(no))+1);
}
}
return res;
}
int main() {
int i, j;
char s[20];
for(i = 0; i < 64; i++) {
//if(low2bit.find((1ULL<<i)%1007) != low2bit.end())
// puts("XX");
low2bit[(1ULL<<i)%1007] = i;
}
while(scanf("%d %d", &n, &m) == 2) {
if(n == 0) break;
for(i = 0; i < m; i++) {
scanf("%s", s);
obj[i] = 0;
for(j = 0; s[j]; j++) {
if(s[j] != '0')
obj[i] |= 1ULL<<j;
}
}
for(i = (1<<n)-1; i >= 0; i--)
dp[i].clear();
ELE node(0,m,0,0);
for(i = 0; i < m; i++) {
if(i >= 64)
node.obj2 |= 1ULL<<(i-64);
else
node.obj1 |= 1ULL<<i;
}
printf("%d\n", dfs(node));
}
return 0;
}