地球的一批村里人正在B站上考古。 该区域的地面坚硬如石、平整如镜。 管理人员为方便，建立了标准的直角坐标系。 每个村里人都各有特长、身怀绝技。 他们感兴趣的内容也不相同。 经过各种测量，每个村里人都会报告一个或多个矩形区域，作为优先考古的区域。 矩形的表示格式为 (x1,y1,x2,y2)，代表矩形的两个对角点坐标。 为了醒目，总部要求对所有村里人选中的矩形区域涂黄色油漆。 牧之并不需要当油漆工，只是他需要计算一下，一共要耗费多少油漆 注意，各个矩形间可能重叠。 ###输入格式 第一行，一个整数 n，表示有多少个矩形。 接下来的 n 行，每行有 4 个整数 x1,y1,x2,y2，空格分开，表示矩形的两个对角顶点坐标。 ###输出格式 一行一个整数，表示矩形覆盖的总面积。 #数据范围： 1≤n≤10000, 0≤x1,x2,y2,y2≤10000 #数据保证：x1<x2 且 y1<y2
共 1 条回复
#include<bits/stdc++.h> using namespace std; const int N=10; int n,k; long long f[N+1][1<<N][N*N+1]; vector trans[1<<N]; int main(){ ios::sync_with_stdio(flase),cin.tie(0); cin>>n>>k; for(int i=0;i<(1<<n);i++){ if(i&i<<1) continue; for(int j=0;j<(1<<n);j++) if(!(j&j<<1)&&!(i&j)&&!(i&j>>1)&&!(i&j<<1)) trans[i].push_back(j); } f[0][0][0]=1; for(int i=1;i<=n+1;i++){ for(int mask=0;mask<(1<<n);mask++) for(auto st:trans[mask]){ f[i][mask][j]+=f[i-1][st][j-_builtin_popcount(mask)]; } } }