【第12题】代码分享：大水题，[COCI2015-2016#2] GEPPETTO

小码匠

发布于 2023-11-24 15:33:36

1800

发布于 2023-11-24 15:33:36

文章被收录于专栏：小码匠和老码农小码匠和老码农

大家好，我是小码匠，今天继续分享的是一道非常简单状压DP的题目。

前置知识

状压DP

路漫漫其修远兮，吾将上下而求索

离自己的既定目标：

目标：300道
已完成：12道
待完成：288道

题目描述

官方原题：

洛谷：https://www.luogu.com.cn/problem/P7859

Geppetto 开了一家披萨店，他正在努力做出全市最好的披萨。

Geppetto 用 N 种原材料做比萨，每种原材料只有一个。原材料标号为 1 到 N。做披萨很简单，只要把原材料混合好然后放进烤箱里烤一烤就行了。但 Geppetto 发现一共有 M 对原材料是冲突的，如果一对冲突的原材料混合在一份披萨里，这份披萨就会变得十分难吃。这给他带来了额外的麻烦。

Geppetto 想知道他最多能做多少种不同的比萨。如果一份比萨上有编号为 i 的原材料，而另一份比萨上没有，那么这两份比萨就是不同的。

输入格式

第一行两个整数 N,M，分别表示原材料总数和冲突总数。

接下来 M 行，每行两个整数

x_i,y_i

，表示一对冲突中两种原材料的编号。

输出格式

一行一个整数，表示 Geppetto 最多能做多少种披萨。

输入输出样例

输入 #1复制

3 2
1 2
2 3

输出 #1复制

输入 #2复制

3 0

输出 #2复制

输入 #3复制

输出 #3复制

说明/提示

【样例 1 解释】

Geppetto 可以做出以下 4 种披萨：

不过因为 Geppetto 可以不放原材料，所以最多可以做出 5 种披萨。

【样例 2 解释】

没有原材料冲突，所以一共可以做出

2^3

=8 种披萨。

【样例 3 解释】

由于所有原材料都互相冲突，所以 Geppetto 只能放一种原材料或者不放原材料，一共可以做出 1+3=4 种披萨。

【数据范围】

对于 100% 的数据，1≤N≤20，0≤M≤400，

1≤x_i,y_i≤N

，保证

AC代码

#include <bits/stdc++.h>

using namespace std;

struct node {
    int x, y;
} a[405];

void best_coder() {
    int n, m;
    int ans = 0;
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        cin >> a[i].x >> a[i].y;
    }
    for (int i = 0; i < (1 << n); ++i) {
        bool is = false;
        for (int j = 0; j < m; ++j)
            if (i & (1 << (a[j].x - 1)) && i & (1 << (a[j].y - 1))) {
                is = true;
                break;
            }
        if (!is) {
            ++ans;
        }
    }
    cout << ans;
}

void happy_coder() {

}

int main() {
    // 提升cin、cout效率
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    // 小码匠
    best_coder();

    // 最优解
    // happy_coder();

    return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2023-11-23，如有侵权请联系 cloudcommunity@tencent.com 删除

cin