[SCOI2009]围豆豆

DP 状压DP

题面

戳我

解析

豆子数这么少，肯定状压啊。
于是设$f[x][y][s]$表示到了$(x,y)$这个点，包围豆子情况为$s$的方案数。
枚举一下出发点和最终豆子选取状态即可。
复杂度$O(n^22^d)$。

嗯，$yy$得很美好，然后不会判断豆子是否被包围。。。。。。。
实际上，判断一个点在一个多边形内的标准，就是它朝一个方向走会与多边形的边相交奇数次。
因为每次跨越边界都是从多边形内(外)到多边形外(内）。
姑且钦定这个方向为正右。
然后自己把握一下线的位置就行（如豆子中心偏下，反正不能与边界重叠）。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#define ll long long
#define re register
#define il inline
#define fp(i,a,b) for(re int i=a;i<=b;++i)
#define fq(i,a,b) for(re int i=a;i>=b;--i)
using namespace std;
const int N=12;
int n,m,d,w[N],f[N][N][1<<10],ans,M,sum[1<<10],mx[4]={1,-1,0,0},my[4]={0,0,1,-1},X[N],Y[N];
char s[N][N];
bool vis[N][N][1<<10];
struct dat{int x,y,S;};
queue<dat>Q;
il ll gi()
{
  re ll x=0,t=1;
  re char ch=getchar();
  while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  if(ch=='-') t=-1,ch=getchar();
  while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  return x*t;
}
il int GetSS(re int x,re int y,re int xx,re int yy,re int S)
{
  fp(i,0,d-1)
    if(((x==X[i]&&xx<X[i])||(x<X[i]&&xx==X[i]))&&y>Y[i]) S^=(1<<i);
  return S;
}
il void BFS(re int x,re int y)
{
  memset(f,63,sizeof(f));f[x][y][0]=0;
  Q.push((dat){x,y,0});vis[x][y][0]=1;
  while(!Q.empty())
    {
      re int x=Q.front().x,y=Q.front().y,S=Q.front().S;Q.pop();
      fp(i,0,3)
    {
      re int xx=x+mx[i],yy=y+my[i];
      if(s[xx][yy]!='0') continue;
      re int SS=(i<2)?GetSS(x,y,xx,yy,S):S;
      if(f[xx][yy][SS]>f[x][y][S]+1)
        {
          f[xx][yy][SS]=f[x][y][S]+1;
          if(!vis[xx][yy][SS]) vis[xx][yy][SS]=1,Q.push((dat){xx,yy,SS});
        }
    }
      vis[x][y][S]=0;
    }
  fp(i,0,M)
    ans=max(ans,sum[i]-f[x][y][i]);
}
int main()
{
  n=gi();m=gi();d=gi();M=(1<<d)-1;
  fp(i,0,d-1) w[i]=gi();
  memset(s,'#',sizeof(s));
  fp(i,1,n) scanf("%s",s[i]+1),s[i][m+1]='#';
  fp(i,1,n)
    fp(j,1,m)
    if(s[i][j]>='1'&&s[i][j]<='9') X[s[i][j]-'1']=i,Y[s[i][j]-'1']=j;
  fp(i,0,M)
    fp(j,0,d-1)
    if(i&(1<<j)) sum[i]+=w[j];
  fp(i,1,n) fp(j,1,m) if(s[i][j]=='0') BFS(i,j);
  printf("%d\n",ans);
  return 0;
}