双周赛 – 25 – 每个人戴不同帽子的方案数

我我我又带着我光滑无褶皱的大脑回来了…好久不做题orz。

4. 每个人戴不同帽子的方案数

总共有 n 个人和 40 种不同的帽子,帽子编号从 140
给你一个整数列表的列表 hats ,其中 hats[i] 是第 i 个人所有喜欢帽子的列表。
请你给每个人安排一顶他喜欢的帽子,确保每个人戴的帽子跟别人都不一样,并返回方案数。
由于答案可能很大,请返回它对 10^9 + 7 取余后的结果。

样例

示例 1:

输入:hats = [[3,4],[4,5],[5]]
输出:1
解释:给定条件下只有一种方法选择帽子。
第一个人选择帽子 3,第二个人选择帽子 4,最后一个人选择帽子 5。

示例 2:

输入:hats = [[3,5,1],[3,5]]
输出:4
解释:总共有 4 种安排帽子的方法:
(3,5),(5,3),(1,3) 和 (1,5)

示例 3:

输入:hats = [[1,2,3,4],[1,2,3,4],[1,2,3,4],[1,2,3,4]]
输出:24
解释:每个人都可以从编号为 1 到 4 的帽子中选。
(1,2,3,4) 4 个帽子的排列方案数为 24 。

示例 4:

输入:hats = [[1,2,3],[2,3,5,6],[1,3,7,9],[1,8,9],[2,5,7]]
输出:111

提示

  • n == hats.length
  • 1 <= n <= 10
  • 1 <= hats[i].length <= 40
  • 1 <= hatsi <= 40
  • hats[i] 包含一个数字互不相同的整数列表。

思路

【状态压缩】

感觉之前有做过类似题还写过博客,然鹅我……

这道题有一个转化,按照正常思路来讲,会把帽子状态压缩,但是帽子最多可以有 40 顶,所以不能状压。转换思路,让帽子去找主人,把人是否带上帽子进行状态压缩。

所谓状态压缩,就是把每个状态表示为一个二进制位。看题目中的数据范围 1 <= n <= 10 ,显然是可以状压的,状态的最大值也不过是 1111111111b = 10000000000b - 1b = 2^11 - 1 = 2047

【状态表示】

dp[i][bits] 表示前 i 顶帽子已经分配给指定的人 / 确定不分配给任何人,且当前所有人戴帽子的状态为 bits

【状态转移】

每次状态转移,将 dp[i][bits] 转移到 dp[i+1][n_bits] ,分两种情况:

  • i + 1 顶帽子分配给某个人 j ,那么 n_bits = bits | (1 << j) 。前提是:

    • j 喜欢帽子 i + 1
    • j 没有被分配过帽子,即 (bits >> j) & 1 == 0
  • i + 1 顶帽子不分配给任何人, 那么 bits = n_bits

【初始化】

  • dp 数组清空为 0
  • dp[0][0] = 1 表示前 0 顶帽子没有分配给任何人的方案数为 1

代码

const int MOD = 1e9 + 7;
int dp[45][1<<10];
class Solution {
public:
    int numberWays(vector<vector<int>>& hats) {
        int n = hats.size();
        int lim = 1 << n;

        for(int i=0; i<=40; i++) for(int s=0; s<lim; s++) dp[i][s] = 0;
        dp[0][0] = 1;

        for(int h=1; h<=40; h++) {
            for(int s=0; s<lim; s++) {
                if(dp[h-1][s] == 0) continue;
                for(int i=0; i<n; i++) {
                    bool flag = false;
                    for(auto v: hats[i]) if(v == h) flag = true;
                    if(!flag) continue;

                    if((s>>i) & 1) continue;

                    int ns = s | (1<<i);
                    dp[h][ns] = (dp[h][ns] + dp[h-1][s]) % MOD;
                }
            }
            for(int s=0; s<lim; s++) dp[h][s] = (dp[h][s] + dp[h-1][s]) % MOD;
        }
        return dp[40][lim-1];
    }
};
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇