题解 P1790 【矩形分割】

这题刚拿到，发现可以用dfs枚举切割点，但是一看数据范围，1≤a≤6，2≤b≤6?自然想到了打表，所以就打了一个表，然后就表过了此题，时间范围O(1)，空间范围O(答案),(比dfs不知道快到哪里去了)

代码:

include<bits/stdc++.h>

using namespace std;
int n,m;
int a[]={1,2,3,4,5,6,15,28,45,66,15,52,143,350,799,28,143,614,2431,9184,45,350,2431,16000,102147,66,799,9184,102147,1114394};//发现不会用二维数组存值，所以就用了一维的，用的时候直接输出a[(n-1)5+(m-2)]就好了
int main(){
scanf("%d%d",&n,&m);//把n,m读入
printf("%d",a[(n-1)5+(m-2)]);//因为5个一组，有(N-1)组，又是第(m-2)个，所以(随便带进去几个值试一试后发现)(划掉)有了这个式子
}
···