神坑的一道题，写了三遍。
两点半开始写的，
第一遍是直接维护两行的二进制。理论上是没问题的，看POJ discuss 上也有人实现了，但是我敲完后准备开始调了。然后就莫名其妙的以为会超时，就删掉了。
第二遍是想错了，因为和之前写过的一道题很像，那道题的正方形最中间不重合即可，所以我以为本质是一样的，然后按照那样的思路写。写写调调到五点半，样例搞掉后，提交，A2T7W1
然后随便找了组数组跟了一下，发现这个方块不允许重合导致这两道题的核心思路差别很大，所以删掉了。
第三遍开始按照自己想的3进制方案写，为了防止再次出现重新写一遍..先找山神问了一下可行性。然后就开始敲，到六点半敲完调完，在校内OJ上交又是各种WA各种TLE，遂弃疗回家，在POJ上看了看发现POJ上的每组数据给了5s，然后发现了几个傻逼错误，改了改终于A调了。
|
Run ID |
User |
Problem |
Result |
Memory |
Time |
Language |
Code Length |
Submit Time |
|
16006693 |
Accepted |
17160K |
11250MS |
3288B |
2016-08-22 21:20:49 |
|||
|
16006635 |
Wrong Answer |
3290B |
2016-08-22 21:10:12 |
|||||
|
16006634 |
Wrong Answer |
3290B |
2016-08-22 21:09:57 |
|||||
|
16006629 |
Wrong Answer |
3290B |
2016-08-22 21:08:53 |
|||||
|
16006549 |
Wrong Answer |
3290B |
2016-08-22 20:56:34 |
|||||
|
16006543 |
Memory Limit Exceeded |
3290B |
2016-08-22 20:55:59 |
不要问我为什么前五次代码长度一摸一样＝＝
不说废话，我说说我的想法，好像效率很低，但是比较好理解吧（至少我很好理解
基本的和普通的状压DP一样，一个线扫下来枚举状态。但是状态的表示用三进制表示用四进制处理，具体实现比较麻烦，可以参考代码。
0->未被覆盖
1->被覆盖
2->被覆盖且下方的方块也被覆盖
剩下的就很好搞了。
时间的话把枚举的状态改成堆或许会好点？
//OJ 1391
//by Cydiater
//2016.8.22
#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <iomanip>
#include <queue>
#include <map>
#include <algorithm>
using namespace std;
#define ll long long
#define up(i,j,n) for(ll i=j;i<=n;i++)
#define down(i,j,n) for(ll i=j;i>=n;i--)
<<;
const int oo=0x3f3f3f3f;
inline ll read(){
,f=;
;ch=getchar();}
+ch-';ch=getchar();}
return x*f;
}
ll N,M,K,f[][MAXN],ans=,T;
][];
namespace solution{
void print(ll s){
ll a[];
memset(a,,sizeof(a));
down(i,M,){
a[i]=s%;
s/=;
}
up(i,,M)cout<<a[i];;
puts("");
}
inline ll get(ll s,ll pos){
pos=M-pos-;
ll tmp=s&(<<(pos<<));
tmp>>=(pos<<);
return tmp;
}
inline ll updata(ll s,ll st,ll nd,ll num){
ll ss=st,n=nd;
st=M-n-;nd=M-ss-;
up(i,st,nd)s|=(num<<(i<<));
return s;
}
void init(){
memset(f,,sizeof(f));
memset(flag,,sizeof(flag));
N=read();M=read();K=read();
ans=;
up(i,,K){
ll x=read(),y=read()-;
flag[x][y]=;
}
}
bool check(ll x,ll st,ll nd,ll s){
||st>=M||nd<||nd>=M||x<=||x>N) ;
up(i,st,nd);/*special case*/
up(i,st,nd)) ;
;
}
void dfs(ll x,ll y,ll s,ll now,ll k){
){
f[x%][now]=max(f[x%][now],f[(x%)^][s]+k);
ans=max(ans,f[x%][now]);
/*puts("s:");print(s);puts("now:");print(now);
printf("x:%d f[x%%2][now]:%d ",x,f[x%2][now]);
cout<<"k:"<<k<<" ans:"<<ans<<endl<<endl;*/
return;
}
//cout<<now<<endl;
){
now|=(<<((M-y-)<<));
dfs(x,y-,s,now,k);
return;
}
,y-,y+,s),y+,now),s,updata(now,y-,y+,),k+);
,y,y+,s),now)][y]&&!flag[x+][y+]&&x+<=N,s,updata(now,y,y+,),k+);
dfs(x,y-,s,now,k);
}
void dp(){
f[][]=;
up(i,,N){
up(s,,(<<(M<<))-)f[(i%)^][s]=;
up(s,,(<<(M<<))-)][s]>)dfs(i+,M-,s,,);
}
}
void output(){
cout<<ans-<<endl;
}
}
int main(){
//freopen("input.in","r",stdin);
//freopen("output.out","w",stdout);
using namespace solution;
T=read();
while(T--){
init();
dp();
output();
}
;
}