FZU 2092 收集水晶 dp+bfs

时间：2022-11-01 06:43:45

定义dp[t][x1][y1][x2][y2]为在t时刻，人走到x1,y1,影子走到x2,y2所获得最大价值

最终就是所有的dp[max][..][..][..][..]的最大值

然后递推也很自然，枚举人和影子的动向，唯一注意的是当走到一点时，只获得一次价值，要除以2

然后对于每一层时间，其实有效的很少，所以用bfs取有效点更新，这样可以减少一些时间复杂度，最终跑出来1593ms

#include <stdio.h>

#include <iostream>

#include <vector>

#include <math.h>

#include <queue>

#include <algorithm>

#include <string.h>

#include <string>

using namespace std;

typedef long long LL;

const int N=1e2+;

const int INF=0x3f3f3f3f;

int dx[]= {,,,-,};

int dy[]= {,-,,,};

char s[][];

int mp[][][];

int dp[][][][][];

bool vis[][][][][];

int n,m,p,mx;

struct Node

{

    int t,x,y,k1,k2;

    Node() {}

    Node(int a,int b,int c,int d,int e)

    {

        t=a,x=b,y=c,k1=d,k2=e;

    }

};

queue<Node>q;

void bfs()

{

    memset(dp,-,sizeof(dp));

    memset(vis,,sizeof(vis));

    while(!q.empty())q.pop();

    dp[][][][][]=;

    vis[][][][][]=;

    Node a,tmp;

    q.push(Node(,,,,));

    while(!q.empty())

    {

        a=q.front();

        q.pop();

        if(a.t==mx)continue;

        tmp.t=a.t+;

        int o=dp[a.t][a.x][a.y][a.k1][a.k2];

        for(int i=; i<; ++i)

            for(int j=; j<; ++j)

            {

                tmp.x=a.x+dx[i],tmp.y=a.y+dy[i];

                tmp.k1=a.k1+dx[j],tmp.k2=a.k2+dy[j];

                if(tmp.x<||tmp.x>n||tmp.y<||tmp.y>m)continue;

                if(tmp.k1<||tmp.k1>n||tmp.k2<||tmp.k2>m)continue;

                if(s[tmp.x][tmp.y]=='#'||s[tmp.k1][tmp.k2]=='#')continue;

                int c=mp[tmp.t][tmp.x][tmp.y]+mp[tmp.t][tmp.k1][tmp.k2];

                if(tmp.x==tmp.k1&&tmp.y==tmp.k2)c/=;

                c+=o;

                if(c>dp[tmp.t][tmp.x][tmp.y][tmp.k1][tmp.k2])

                {

                    dp[tmp.t][tmp.x][tmp.y][tmp.k1][tmp.k2]=c;

                    if(!vis[tmp.t][tmp.x][tmp.y][tmp.k1][tmp.k2])

                    {

                        q.push(tmp);

                        vis[tmp.t][tmp.x][tmp.y][tmp.k1][tmp.k2]=;

                    }

                }

            }

    }

}

int main()

{

    int T;

    scanf("%d",&T);

    while(T--)

    {

        mx=;

        scanf("%d%d",&n,&m);

        for(int i=; i<=n; ++i)

            scanf("%s",s[i]+);

        memset(mp,,sizeof(mp));

        scanf("%d",&p);

        for(int i=; i<p; ++i)

        {

            int t,x,y,v;

            scanf("%d%d%d%d",&t,&x,&y,&v);

            mx=max(mx,t);

            mp[t][x][y]+=v;

        }

        bfs();

        int ans=;

        for(int i=; i<=n; ++i)

            for(int j=; j<=m; ++j)

                for(int k1=; k1<=n; ++k1)

                    for(int k2=; k2<=m; ++k2)

                        ans=max(ans,dp[mx][i][j][k1][k2]);

        printf("%d\n",ans);

    }

    return ;

}

相关文章