题解 P3356 【火星探险问题 】
wuzhoupei
2018-01-17 18:06:52
这个题是【网络流24题】中的一道；
然而我一看这个题就去想 DP 了；
所以呢，我写一个 DP 的题解；
首先，由于每个车可以走下和右两个方向；
而且每个格子可以被任意多的车走；
唯一的限制是有障碍的的地方不能走；
这是路径的限制；
还有石头只能取一次；
所以我们就做一个DP；
来求一条由 (1,1) 到 (n,m) 的路径；
使得这个路径上的石头最多；
这就是个裸的 DP 了；
只需要记录当前点是从哪个点转移过来的；
最后 dfs 输出就好了；
~~DP 结束，然而不会这道题的网络流。。。。~~
-------------------------------
```cpp
#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);
}
```