【bzoj4715】囚人的旋律 dp

题目描述

给你一个 $1\sim n$ 的排列 $a_i$ ，若 $i\le j$ 且 $a_i\ge a_j$ ，则 $i$ 到 $j$ 有一条边。现在给你这张图，求既是独立集（任意两个选定点都没有边）又是覆盖集（任意一个非选定点都存在一个选定点与之相连）的点集数模 $10^9+7$ 。

输入

输入第一行含有两个整数n和m，表示逆序图的点数和边数。

接下来m行，每行描述一条边。每行包含两个1～n的整数，代表边的两个端点。保证没有重边和自环。

保证给定的图是一个合法的逆序图，即，存在至少一个序列，按照题目描述中所述方法得到的逆序图是给定的图。

n≤1000，0≤m≤(n(n-1))/2

输出

输出一个整数，表示方案数对1,000,000,007取模得到的结果。

样例输入

5 5
2 4
2 5
1 4
3 4
3 5

样例输出

题解

我们去 %CQzhangyu 吧

#include <cstdio>

#include <algorithm>

#define mod 1000000007

using namespace std;

int v[1010][1010] , f[1010];

int main()

{

	int n , m , i , j , k , x , y , ans = 0;

	bool flag;

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

	for(i = 1 ; i <= m ; i ++ ) scanf("%d%d" , &x , &y) , v[min(x , y)][max(x , y)] = 1;

	for(i = 1 ; i <= n ; i ++ ) v[0][i] = 1;

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

	{

		if(!f[i]) f[i] = 1;

		flag = 0;

		for(k = 0 , j = i + 1 ; j <= n ; j ++ )

		{

			if(!v[i][j])

			{

				flag = 1;

				if(v[k][j]) k = j , f[j] = (f[j] + f[i]) % mod;

			}

		}

		if(!flag) ans = (ans + f[i]) % mod;

	}

	printf("%d\n" , ans);

	return 0;

}

巴特西

【bzoj4715】囚人的旋律 dp

最新文章

热门文章