solution-code1901

1
#include <iostream>
2
#include <cstdio>
3
#include <cstring>
4
#include <algorithm>
5
using namespace std;
6
int f[2][(1<<14)+5];
7
bool a[15][15];
8
int main(void)
9
{
10
  int i,j,S,n,m,x,ch,cnt=1,pre=0,ans=0;
11
  scanf("%d%d",&n,&m);
12
  memset(a,1,sizeof(a));
13
  memset(f[cnt],-1,sizeof(f[cnt]));
14
  for(i=1;i<=m;++i)
15
  {
16
    while(ch=getchar())if(ch>='A'&&ch<='Z')break;
17
    scanf("%d",&x);
18
    a[ch-'A'][x-1]=0;
19
  }
20
  f[cnt][0]=0;
21
  m=n<<1;
22
  for(i=0;i<n;++i)
23
  {
24
    for(j=0;j<m;++j)
25
    {
26
      pre^=1;cnt^=1;
27
      memset(f[cnt],-1,sizeof(f[cnt]));
28
      for(S=0;S<(1<<m);++S)
29
      {
30
        if(a[i][j])
31
        {
32
          f[cnt][S]=f[pre][S^(1<<j)];
33
          if(!(S&(1<<j)))
34
          {
35
            if(j>0&&!(S&(1<<(j-1))))f[cnt][S]=max(f[cnt][S],f[pre][S^(1<<(j-1))]);
36
            if(f[cnt][S]>=0)++f[cnt][S];
37
            f[cnt][S]=max(f[cnt][S],f[pre][S]);
38
          }
39
        }
40
        else f[cnt][S]=S&(1<<j)?-1:f[pre][S];
41
      }
42
    }
43
  }
44
  for(i=(1<<n);i<(1<<m);++i)f[cnt][i&((1<<n)-1)]=max(f[cnt][i&((1<<n)-1)],f[cnt][i]);
45
  for(i=n;i<m;++i)
46
  {
47
    for(j=0;j<n;++j)
48
    {
49
      pre^=1;cnt^=1;
50
      memset(f[cnt],-1,sizeof(f[cnt]));
51
      for(S=0;S<(1<<n);++S)
52
      {
53
        if(a[i][j])
54
        {
55
          f[cnt][S]=f[pre][S^(1<<j)];
56
          if(!(S&(1<<j)))
57
          {
58
            if(j>0&&!(S&(1<<(j-1))))f[cnt][S]=max(f[cnt][S],f[pre][S^(1<<(j-1))]);
59
            if(f[cnt][S]>=0)++f[cnt][S];
60
            f[cnt][S]=max(f[cnt][S],f[pre][S]);
61
          }
62
        }
63
        else f[cnt][S]=S&(1<<j)?-1:f[pre][S];
64
      }
65
    }
66
  }
67
  for(i=0;i<(1<<n);++i)ans=max(ans,f[cnt][i]);
68
  printf("%d\n",ans);
69
  return 0;
70
}