洛谷2566 [SCOI2009]围豆豆

Luogu

BZOJ

分析

这题思路好神仙啊qwq

前置知识

如何判断一个点是否在一个多边形内部?从这个点向外引一条射线,若与多边形相交了奇数次,就在它的内部,否则在外部。

正解

$d$很小,考虑状压DP。

预处理出豆子的坐标和每个状态下所有豆子的得分和$sum[S]$。

首先枚举一个起点$(x,y)$。设$f[i][j][S]$表示走到了$(i,j)$这个格子,当前圈住的豆子的状态为$S$的最小边界长度。显然这个东西可以跑一遍最短路得到,具体实现还是见代码。

然后,枚举状态$S$。因为要走一条回路,所以用$sum[S]-f[x][y][S]$来更新答案。

最后输出答案,然后就做完啦。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int fx[4][2]={1,0,-1,0,0,1,0,-1};

int n,m,d,ans=-2e9;
int f[15][15][1<<9]; //f[i][j][S]表示当前在(i,j),围住的豆豆状态为S的最小边界长度
int sum[1<<9]; //sum[S]表示S状态的总分
char g[15][15];
int val[15],X[15],Y[15];

struct node { int x,y,S; };
int inq[15][15][1<<9];


inline int get(int x,int y,int xx,int yy,int S) {
    for (re int i=0;i<d;++i)
        if (((x==X[i]&&xx>X[i])||(x>X[i]&&xx<=X[i]))&&yy>Y[i]) S^=1<<i;
    return S;
}

inline void solve(int x,int y) {
    queue<node> Q; Q.push((node){x,y,0});
    memset(f,0x3f,sizeof(f)); f[x][y][0]=0,inq[x][y][0]=1;
    while (!Q.empty()) {
        node fr=Q.front(); Q.pop();
        int x=fr.x,y=fr.y,S=fr.S; inq[x][y][S]=0;
        for (re int i=0;i<4;++i) {
            int X=x+fx[i][0],Y=y+fx[i][1];
            if (g[X][Y]!='0') continue;
            int SS=i<2?get(x,y,X,Y,S):S;
            if (f[x][y][S]+1<f[X][Y][SS]) {
                f[X][Y][SS]=f[x][y][S]+1;
                if (!inq[X][Y][SS]) {
                    inq[X][Y][SS]=1;
                    Q.push((node){X,Y,SS});
                }
            }
        }
    }
    for (re int S=0;S<(1<<d);++S)
        ans=max(ans,sum[S]-f[x][y][S]);
}

int main() {
    n=read(),m=read(),d=read();
    for (re int i=0;i<d;++i) val[i]=read();
    for (re int i=1;i<=n;++i) scanf("%s",g[i]+1);
    for (re int i=0;i<=n+1;++i) g[i][0]=g[i][m+1]='#';
    for (re int i=0;i<=m+1;++i) g[0][i]=g[n+1][i]='#';
    for (re int S=0;S<(1<<d);++S)
        for (re int i=0;i<d;++i)
            if (S&(1<<i)) sum[S]+=val[i];
    for (re int i=1;i<=n;++i)
        for (re int j=1;j<=m;++j)
            if (g[i][j]>='1'&&g[i][j]<='9')
                X[g[i][j]-'1']=i,Y[g[i][j]-'1']=j;
    for (re int i=1;i<=n;++i)
        for (re int j=1;j<=m;++j)
            if (g[i][j]=='0') solve(i,j);
    printf("%d\n",ans);
    return 0;
}
最后修改:2019 年 09 月 24 日 08 : 57 PM

发表评论