链接
题意
有1个初始武器,$n (1 \leq n \leq 16)$个敌人,击败每个敌人之后都会获得新的武器,每个武器所能击败的敌人也不同,给出每个武器能击败的敌人,输出最终击败所有敌人的方法总数。
思路
用二进制数表示当前状态。定义$dp[i]、sta[i]$分别表示击败敌人的集合为$i$时的方法总数和武器所能击败的敌人的集合。每个状态可以转移至击败一名新的敌人之后的状态,时间复杂度$O(n2^n)$。
代码
|
|
A little brute force is always helpful.
有1个初始武器,$n (1 \leq n \leq 16)$个敌人,击败每个敌人之后都会获得新的武器,每个武器所能击败的敌人也不同,给出每个武器能击败的敌人,输出最终击败所有敌人的方法总数。
用二进制数表示当前状态。定义$dp[i]、sta[i]$分别表示击败敌人的集合为$i$时的方法总数和武器所能击败的敌人的集合。每个状态可以转移至击败一名新的敌人之后的状态,时间复杂度$O(n2^n)$。
|
|