rt，外网题，但它是CEOI2002，http://poj.org/problem?id=1038，状压DP入门题，但不知道为什么一些数据过不了，比如：

1
110 5 7
50 3
52 1
70 4
85 4
9 1
76 5
12 1

因为感觉题目本应挺简单，所以放到灌水区问……

望好心人救助！

#include <bits/stdc++.h>
#define int short 
using namespace std;
struct node { int s1,s2,occ1,occ2; }options[275];
int p[151],cnt[1024],f[151][275][275];
int max(int a,int b){return a>b?a:b;}
signed main()
{
	int T;
	cin>>T;
	while(T--){
		memset(cnt,0,sizeof(cnt));
		memset(p,0,sizeof(p));
		memset(f,0,sizeof(f));
		int n,m,k,tx,ty,num=0;
		cin>>n>>m>>k;
		for(int i=1;i<=k;i++){
			cin>>tx>>ty;
			p[tx]|=(1<<m-ty);
		}
		p[n+1]=(1<<m)-1;
		if(n==1){cout<<"0\n";continue;}
		for(int s=0,x=0;s<(1<<m);s++,x=s) while(x) cnt[s]+=(x&1),x>>=1;
		for(int s1=0;s1<(1<<m);s1++) if(!(s1&(s1>>1)|s1&(s1>>2)|(s1>>1)&(s1>>2)) && !(s1&1) && !(s1&2))
			for(int s2=0;s2<(1<<m);s2++) if(!(s2&(s2>>1)) && !(s2&1)){
				int occ1=s1|(s1>>1)|(s1>>2),occ2=s2|(s2>>1);
				if(occ1&occ2) continue;
				options[++num]={s1,s2,occ1,occ2};
			}
		for(int i=1;i<=num;i++){
			if((options[i].occ1|options[i].occ2)&p[1]) continue;
			if((options[i].occ1&p[2]) || (options[i].occ2&p[2]) || (options[i].occ2&p[3])) continue;
			f[1][1][i]=cnt[options[i].s1]+cnt[options[i].s2];
		}
		if(n==2){
			int ans=0;
			for(int i=1;i<=num;i++) ans=max(ans,f[1][1][i]);
			cout<<ans<<endl;
			continue;
		}
		for(int x=1;x<=num;x++) if(x==1 || f[1][1][x])
			for(int y=1;y<=num;y++){
				if((options[y].occ1|options[y].occ2)&p[2]) continue;
				if((options[y].occ1&p[3]) || (options[y].occ2&p[3]) || (options[y].occ2&p[4])) continue;
				if((options[x].occ1|options[x].occ2)&(options[y].occ1|options[y].occ2)) continue;
				f[2][x][y]=f[1][1][x]+cnt[options[y].s1]+cnt[options[y].s2];
			}
		for(int i=3;i<=n-1;i++)
			for(int x=1;x<=num;x++)
				for(int y=1;y<=num;y++) if(f[i-1][x][y])
					for(int z=1;z<=num;z++){
						if((options[z].occ1|options[z].occ2)&p[z]) continue;
						if((options[z].occ1&p[i+1]) || (options[z].occ2&p[i+1]) || (options[z].occ2&p[i+2])) continue;
						if(options[x].occ2&(options[z].occ1|options[z].occ2)) continue;
						if((options[y].occ1|options[y].occ2)&(options[z].occ1|options[z].occ2)) continue;
						f[i][y][z]=max(f[i][y][z],f[i-1][x][y]+cnt[options[z].s1]+cnt[options[z].s2]);
					}
		int ans=0;
		/*for(int i=1;i<n;i++){int dd=0;
		for(int x=1;x<=num;x++) for(int y=1;y<=num;y++)dd=max(dd,f[i][x][y]);cout<<dd<<endl;
		}*/
		for(int x=1;x<=num;x++) for(int y=1;y<=num;y++) ans=max(ans,f[n-1][x][y]);
		cout<<ans<<endl;
	}
	return 0;
}