这几天在学习提高课的状态压缩DP部分，感觉棋盘式的比较好接受，集合式的有点难，看完课程后想起来当年一道当时没有做出来的题目也许可以用状态压缩DP做，然后试了试，一发通过啦。

感觉这道题是非常好的练习状态压缩DP的题目，非常适合我这样的萌新练手。

原题链接：https://atcoder.jp/contests/abc142/tasks/abc142_e

题目的大致翻译

我们有 N 个盒子，编号 1 - N。

一家商店卖 M 个钥匙，第i个钥匙的售价是$a_i$元，他分别可以打开$b_i$个箱子，
对应的编号是$c_{i_1}$-$c_{i_{b_i}}$号，求问打开所有箱子最少需要多少钱，如果没办法打开所有箱子的话输出$-1$。

后面懒得翻译了（
数据范围和标准输入输出请大家康康原题吧。。。

本弱鸡思路

注意题目是1-index的，所以我的代码中把所有的编号都前移了一个，影响大家阅读很抱歉。

首先我们需要思考我们的数据要如何储存，以及要什么样的数据。

1. 储存钥匙的价格在向量prices中，其中prices[i]代表第i把钥匙的价格；

2. 储存每把钥匙可以开的箱子编号，储存在向量keys中，其中keys[i]代表第i把钥匙可以开的箱子
   编号，这里我们使用二进制数储存，也就是如果第k位是1代表可以打开k号箱子，是0代表打不开；

3. 我们还需要储存一个映射关系，就是第i号箱子可以用哪个钥匙打开，用二维向量corr（秘制命名）储存，其中corr[i]对应的是第i号箱子可以用哪些编号的钥匙打开；

接下来我们需要思考状态转移的问题，这里有点像愤怒的小鸟一题，我们用向量dp来储存，其中dp[state]储存的是可以打开的箱子对应的状态为state的最低需要花销。

再接下来结合代码讲解转移思路：

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
int main(){
    int n, m;
    cin >> n >> m;
    int max_state = 1 << n; //max_state - 1对应的是全部都可以打开的情形
    vector<int> prices (m, 0);
    vector<int> keys (m, 0);
    vector<vector<int>> corr (n, vector<int> {});
    for(int i = 0; i < m; i ++)
    {
        int price, nums;
        cin >> price >> nums;
        prices[i] = price;
        for(int j = 0; j < nums; j ++)
        {
            int bit;
            cin >> bit;
            keys[i] += (1 << (bit-1));
            corr[bit-1].push_back(i);
        }
    } //以上是处理输入；
    vector<int> dp (max_state, 0x3f3f3f3f); //初始化开销为很大的金额
    dp[0] = 0; //很重要，什么都不开是不需要花销的
    for(int state = 0; state < max_state - 1; state ++) //我们遍历所有的状态，注意不需要处理全部都可以打开的情形
    {
        int x = 0;
        for(int i = 0; i < n; i ++)
        {
            if(!(state >> i & 1))
            {
                x = i;
                break;
            }
        } //随便选一个当前状态没办法打开的箱子

        if(corr[x].size() == 0)
        {
            cout << -1 << endl;
            return 0;
        } //如果没有钥匙可以打开这个箱子，就直接输出-1结束了

        for(int key: corr[x]){
            dp[state|keys[key]] = min(dp[state|keys[key]], dp[state] + prices[key]);
        } //转移过程：我们遍历所有的可以打开x号箱子的钥匙，然后更新的状态，因为打开x的
        //可能还能打开其他箱子，那么打开哪些呢？自然是state|keys[key]啦，就更新这个状态；
    }
    cout << dp[max_state - 1] << endl; //最后输出全部打开的情形；
    return 0;
}

就是这样啦，推荐像我一样的萌新用来练手