T526 优美的队列

8/16/2021 10:28:54 PM

题目

假设有从 1 到 N 的 N 个整数，如果从这 N 个数字中成功构造出一个数组，使得数组的第 i 位 (1 <= i <= N) 满足如下两个条件中的一个，我们就称这个数组为一个优美的排列。条件：

第 i 位的数字能被 i 整除
i 能被第 i 位上的数字整除

现在给定一个整数 N，请问可以构造多少个优美的排列？

示例1:

输入: 2
输出: 2
解释:

第 1 个优美的排列是 [1, 2]:
第 1 个位置（i=1）上的数字是1，1能被 i（i=1）整除
第 2 个位置（i=2）上的数字是2，2能被 i（i=2）整除

第 2 个优美的排列是 [2, 1]:
第 1 个位置（i=1）上的数字是2，2能被 i（i=1）整除
第 2 个位置（i=2）上的数字是1，i（i=2）能被 1 整除

说明:

N 是一个正整数，并且不会超过15。

题解:

Key Word : 状压DP、位运算

    class Solution {
	public:
    int countArrangement(int n) {
        const int m = 1 << n;  //m表示状态数
        int dp[16][m];//dp[i][j] //表示遍历到第i个数字时 j选取状态下一共多少种排列
        memset(dp, 0, sizeof(dp));
        for(int i = 0; i < n; ++i)  //遍历数字位置
            for(int j = 0; j < m; ++j)  //遍历每一个状态
                if(__builtin_popcount(j) == i)  //如果当前状态所取个数与数字位置一致
                for(int k = 0; k < n; ++k)  //遍历每一个数字，查看哪个符合题目要求
                    if(((k + 1) % (i + 1) == 0 || (i + 1) % (k + 1) == 0) 
						&& ((1 << k) & ~j))  
				 	//如果满足题目条件,更新（i << k) | j中的方法数
                        dp[i][(1 << k) | j] += i == 0 ? 1 : dp[i - 1][j];
        return dp[n - 1][m - 1];
    	}
	};

理解：状压DP首先得看出来:

一般状压DP都和位运算结合
个数比较少，全排列？然后就是二进制表示特征数:16 32 20······
本题：确定好DP数组一个是状态一个是遍历位置，之后就是细节处理比如

首先，遍历位置，决定是第几个才能进行状态转移

然后，遍历枚举状态，因为每一种状态都可能符合条件，求出可行状态

之后，对于每个状态，处理新加的一个位置

wuwuwu有点难