链接:
题意:
有n(n≤128)个物体,m(m≤11)个特征。每个物体用一个m位01串表示,表示每个特征是具备还是不具备。
我在心里想一个物体(一定是这n个物体之一),由你来猜。你每次可以询问一个特征,然后我会告诉你:我心里的物体是否具备这个特征。当你确定答案之后,就把答案告诉我(告知答案不算“询问”)。如果你采用最优策略,最少需要询问几次能保证猜到?例如,有两个物体:1100和0110,只要询问特征1或者特征3,就能保证猜到。
分析:
为了叙述方便,设“心里想的物体”为W。首先在读入时把每个物体转化为一个二进制整数。
不难发现,同一个特征不需要问两遍,所以可以用一个集合k表示已经询问的特征集。在这个集合k中,有些特征是W所具备的,剩下的特征是W不具备的。用集合c来表示“已确认物体W具备的特征集”,则c一定是k的子集。设d(k,c)表示已经问了特征集k,其中已确认W所具备的特征集为c时,还需要询问的最小次数。如果下一次提问的对象是特征i(这就是“决策”),则询问次数为:max{d(k+{i},c+{i}),d(k+{i},c)}+1。考虑所有的i,取最小值即可。边界条件为:如果只有一个物体满足“具备集合c中的所有特征,但不具备集合k-c中的所有特征”这一条件,则d(k,c)=0,因为无须进一步询问,已经可以得到答案。因为c为k的子集,所以状态总数为3^m,时间复杂度为O(m*3^m)。对于每个k和c,可以先把满足该条件的物体个数统计出来,保存在amt[k][c],避免状态转移的时候重复计算。统计amt[k][c]的方法是枚举k和物体,时间复杂度为O(n*2^m),对于本题来说可以忽略不计。
代码:
1 #include2 #include 3 using namespace std; 4 5 const int INF = 0x3f3f3f3f; 6 const int UPM = 11; 7 const int UPN = 128; 8 int n, m, d[1< <