#include <cstdio>
#include <string.h>
using namespace std;
short dp[150][59049],map[150][10];
int N,M,times3[15];
inline int D3(int zt,int y){return (zt%times3[y+1])/times3[y];}
int Ok2(int zt,int x,int y){
    if (y+2>M)return 0;
    if (map[x][y] || map[x][y+1])return 0;
    if (D3(zt,y)<2 || D3(zt,y+1)<2)return 0;
    return 1;
}
int Ok3(int zt,int x,int y){
    if (y+3>M)return 0;
    if (map[x][y] || map[x][y+1] || map[x][y+2])return 0;
    if (D3(zt,y)<1 || D3(zt,y+1)<1 || D3(zt,y+2)<1)return 0;
    return 1;
}
inline int New2zt(int nzt,int y){return nzt | (1<<y) | (1<<(y+1));}
inline int New3zt(int nzt,int y){return nzt | (1<<y) | (1<<(y+1)) | (1<<(y+2));}
int Newzt(int x,int zt,int nzt){int r;r=0;
    for (int i=M-1;i>=0;i--){r*=3;
        if (((nzt & (1<<i))==0) && map[x][i]==0){
           if (D3(zt,i)>=1)r+=2;
           else r+=1;
        }
    }
    return r;
}
int f(int x,int y,int zt,int nzt,int now){
    if (x<0)return 0;
    if (y==0 && dp[x][zt]>=0)return dp[x][zt];
    if (y>=M)return now+f(x-1,0,Newzt(x,zt,nzt),0,0);
    if (y==0)dp[x][zt]=0;
    int tmp,res;
    res=0;
    if (Ok2(zt,x,y)){
       tmp=f(x,y+2,zt,New2zt(nzt,y),now+1);
       if (res<tmp)res=tmp;
    }
    if (Ok3(zt,x,y)){
       tmp=f(x,y+3,zt,New3zt(nzt,y),now+1);
       if (res<tmp)res=tmp;
    }
    tmp=f(x,y+1,zt,nzt,now);
    if (res<tmp)res=tmp;
    if (y==0)dp[x][zt]=res;
    return res;
}
int main()
{
    int T,K,x,y;
    times3[0]=1;
    for (int i=1;i<15;i++)times3[i]=3*times3[i-1];
    scanf("%d",&T);
    while (T--){
          memset(dp,0xff,sizeof(dp));
          memset(map,0,sizeof(map));
          scanf("%d %d %d",&N,&M,&K);
          for (int i=0;i<K;i++){
              scanf("%d %d",&x,&y);
              map[x-1][y-1]=1;
          }
          printf("%d\n",f(N-1,0,0,0,0));
    }
    return 0;
}

• 我最烦那种之贴代码不附算法的人。鄙人算法如下（与fanhqme的算法一样） (175) NeverWin 2008-11-22 17:51:01