noip模拟赛罪犯分组

分析：看了题后没别的思路，感觉就是dp,普通dp的话状态和方程实在是不好设计，观察数据，发现N非常小，暗示了这道题要用状压dp来做.

先枚举每个集合，再用O(n^2)的暴力看这个集合内有多少个冲突，如果冲突数量不大于k,那么就可以分成1个集合了，否则一定要分成多个集合，那么枚举它的子集j,状态转移方程就出来了:f[i] = min{f[j] + f[i ^ j]} j是i的子集.

以后没思路要多往dp上面去想，还要注意看数据范围，有一个值特别小就很有可能是状压dp.

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

const int inf = 0x7fffffff;

int n, m, k,a[][],f[];

int main()

{

    scanf("%d%d%d", &n, &m, &k);

    for (int i = ; i < ( << n); i++)

        f[i] = inf;

    for (int i = ; i <= m; i++)

    {

        int x, y;

        scanf("%d%d", &x, &y);

        a[x][y] = a[y][x] = ;

    }

    for (int i = ; i < ( << n); i++)

    {

        int cnt = ;

        for (int j = ; j <= n; j++)

            for (int l = j + ; l <= n; l++)

                if (a[j][l] && (i & ( << (j - )) && (i & ( << (l - )))))

                    cnt++;

        if (cnt <= k)

            f[i] = ;

        else

        {

            for (int j = i; j; j = (j - ) & i)

                f[i] = min(f[i], f[j] + f[i ^ j]);

        }

    }

    printf("%d\n", f[( << n) - ]);

    return ;

}

巴特西

noip模拟赛罪犯分组

最新文章

热门文章

巴特西

noip模拟赛 罪犯分组

最新文章

热门文章

noip模拟赛罪犯分组