昆山便宜做网站,庄河网站建设,网站软件设计,安徽省建设厅网站电话正题
P7154 题目大意
有n头牛和n个牛棚#xff0c;每头牛可以进入体积大于等于该牛的牛棚#xff0c;当一个所有未进入牛棚的牛都不能再进时#xff0c;称为极大的匹配#xff0c;问你有多少种极大的匹配 解题思路
先把牛棚和牛放到一起#xff0c;然后按体积排序
那么…正题
P7154 题目大意
有n头牛和n个牛棚每头牛可以进入体积大于等于该牛的牛棚当一个所有未进入牛棚的牛都不能再进时称为极大的匹配问你有多少种极大的匹配 解题思路
先把牛棚和牛放到一起然后按体积排序
那么考虑DP
如果一个牛棚没有选那么后面的牛必须全部匹配否则该牛棚可以与其匹配
对于一头牛如果不是必须匹配那前面的牛棚就全选了该牛就可选可不选否则必须选
那么设fi,j,1/0f_{i,j,1/0}fi,j,1/0表示前i个单位还有j个牛棚后面的牛必须选/不一定要选的方案数然后DP即可 code
#includecstdio
#includecstring
#includeiostream
#includealgorithm
#define ll long long
#define wyc 1000000007
#define N 3030
using namespace std;
int n,now,f[N1][N][2];
struct node
{int s,v;
}a[N1];
bool cmp(node x,node y)
{return x.sy.s||x.sy.sx.vy.v;
}
int main()
{scanf(%d,n);for(int i1;in;i){scanf(%d,a[i].s);a[i].v0;}for(int in1;in*2;i){scanf(%d,a[i].s);a[i].v1;}sort(a1,a1n*2,cmp);now0;f[0][0][0]1;for(int i1;in*2;i){if(!a[i].v){for(int j0;jnow;j){(f[i][j][0]f[i-1][j][0])%wyc;;//可以不选if(j){(f[i][j-1][0]1ll*f[i-1][j][0]*j%wyc)%wyc;//也可以选(f[i][j-1][1]1ll*f[i-1][j][1]*j%wyc)%wyc;//必须选}}}else{for(int j0;jnow;j){(f[i][j][1](f[i-1][j][0]f[i-1][j][1])%wyc)%wyc;//不选(f[i][j1][0]f[i-1][j][0])%wyc;(f[i][j1][1]f[i-1][j][1])%wyc;}now;}}printf(%d,(f[n*2][0][0]f[n*2][0][1])%wyc);return 0;
}
