题解 P3356 【火星探险问题 】

这个题是【网络流24题】中的一道;

然而我一看这个题就去想 DP 了;

所以呢,我写一个 DP 的题解;

首先,由于每个车可以走下和右两个方向;

而且每个格子可以被任意多的车走;

唯一的限制是有障碍的的地方不能走;

这是路径的限制;

还有石头只能取一次;

所以我们就做一个DP;

来求一条由 (1,1) 到 (n,m) 的路径;

使得这个路径上的石头最多;

这就是个裸的 DP 了;

只需要记录当前点是从哪个点转移过来的;

最后 dfs 输出就好了;

DP 结束,然而不会这道题的网络流。。。。


#include "iostream"
#include "stdio.h"
#include "algorithm"
#include "queue"
#define II int
#define R register
#define IL inline
#define I 50
using namespace std;

II inq[I][I], dis[I][I], from[I][I], nu[I][I];

II bx[2]={1,0}, by[2]={0,1};

II who,n,m,all;

queue <II> Qx,Qy;

IL void bfs()
{
    for(R II i=1;i<=n;i++)
    {
        for(R II j=1;j<=m;j++)
        {
            dis[i][j]=-1e9;
            from[i][j]=-1;
        }
    }

    dis[n][m]=nu[n][m];
    for(R II x=n;x;x--)
    {
        for(R II y=m;y;y--)
        {
            if(nu[x][y]==-1) continue ;
            for(R II i=1;i>=0;i--)
            {
                R II xx=x+bx[i], yy=y+by[i];
                if(xx && yy && xx<=n && yy<=m && dis[x][y]<=dis[xx][yy]+nu[x][y] && nu[xx][yy]!=-1) {
                    dis[x][y]=dis[xx][yy]+nu[x][y];
                    from[x][y]=i;
                }
            }
        }
    }
}

IL void dfs(R II x,R II y)
{
//    cout<<x<<" "<<y<<endl;
    nu[x][y]=0;
    R II o=from[x][y];
    if(x==n && y==m) return ;
    printf("%d %d\n",who,o);
    dfs(x+bx[o],y+by[o]);
}

int main()
{
    scanf("%d",&all);
    scanf("%d%d",&n,&m);  swap(n,m);
    for(R II i=1;i<=n;i++)
    {
        for(R II j=1;j<=m;j++)
        {
            R II x;
            scanf("%d",&x);
            if(x==1) x=-1;
            nu[i][j]=x;
        }
    }

    for(who=1;who<=all;who++) 
    {
        bfs();
        dfs(1,1);
    }

    exit(0);
}

发表于 2018-01-17 18:06:52 in 题解