NBUT 1673 迷宫问题(DP)

  • [1673] 迷宫问题

  • 时间限制: 1000 ms 内存限制: 65535 K
  • 问题描述
  • Alex的猫咪不小心走进了迷宫,Alex为了心爱的猫咪,决定进入迷宫去解救他的猫咪。

    已知猫咪坐标为(n - 1, m - 1),Alex坐标为(0, 0),Alex只能往下或者往右走,且不能走出迷宫,迷宫的大小为n*m,迷宫每个格子上都有一个数字x,如果x大于0,说明Alex走到这个格子上后,血量增加x;反之血量减少x,要求不论在哪个格子,血量都至少大于等于1,且血量没有上限,问,如果Alex要成功从(0,0)走到(n - 1, m - 1),需要的初始血量最少应该是多少?

  • 输入
  • 先输入 T,说明有T组数据。
    接下来T个case
    每个case上
    输入 n, m(迷宫的大小)(1 <= n, m <= 1000)
    接下来输入迷宫,保证每格都是整型。
    且每个数字绝对值都小于等于100
  • 输出
  • 输出Alex 最小需要的初始血量值。
  • 样例输入
  • 2
    3 3
    2 -1 1
    -1 0 -1
    -1 -1 3
    3 3
    3 -9 7
    -3 -2 -8
    0 -1 0
  • 样例输出
  • 1
    2

题目链接:NBUT 1673

当时周赛那会儿说是DP题……某聚聚几下就A了(膜一下Orz),然而我连学长讲解也没听懂,时隔N个月又回来撸了一发,发现用学长那个DP做不来…………,然后自己在纸上对样例推了下就过了,就是if-else有点多= =……

学长代码好像是逆着推的,我写的是正着推,用结构体记录从起始点到当前点的最低所需血量least和当前最多留下的血now;

先特判起始点,然后对每一个邻接的点都进行判断,选出最低所需血量least最小的前驱点赋值给当前点,然后更新now,看now够不够消耗,够的话就只更新now,不够的话还要把least更新,然后就差不多了。

代码:

#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<sstream>
#include<cstring>
#include<bitset>
#include<cstdio>
#include<string>
#include<deque>
#include<stack>
#include<cmath>
#include<queue>
#include<set>
#include<map>
using namespace std;
#define INF 0x3f3f3f3f
#define CLR(x,y) memset(x,y,sizeof(x))
#define LC(x) (x<<1)
#define RC(x) ((x<<1)+1)
#define MID(x,y) ((x+y)>>1)
typedef pair<int,int> pii;
typedef long long LL;
const double PI=acos(-1.0);
const int N=1010;
int pos[N][N];
struct info
{
int least;
int now;
};
info dp[N][N];
int main(void)
{
int tcase,i,j,n,m;
scanf("%d",&tcase);
while (tcase--)
{
scanf("%d%d",&n,&m);
for (i=0; i<n; ++i)
{
for (j=0; j<m; ++j)
scanf("%d",&pos[i][j]);
}
if(pos[0][0]>=0)
dp[0][0].least=1;
else
dp[0][0].least=-pos[0][0]+1;
dp[0][0].now=dp[0][0].least+pos[0][0];
for (i=0; i<n; ++i)
{
for (j=0; j<m; ++j)
{
if(!i&&!j)
continue;
if(!i)
{
dp[i][j]=dp[i][j-1];
if(dp[i][j-1].now+pos[i][j]>=1)
dp[i][j].now+=pos[i][j];
else
{
int dx=-pos[i][j]+1-dp[i][j-1].now;
dp[i][j].least+=dx;
dp[i][j].now=1;
}
}
else if(!j)
{
dp[i][j]=dp[i-1][j];
if(dp[i-1][j].now+pos[i][j]>=1)
dp[i][j].now+=pos[i][j];
else
{
int dx=-pos[i][j]+1-dp[i-1][j].now;
dp[i][j].least+=dx;
dp[i][j].now=1;
}
}
else
{
info a=dp[i-1][j],b=dp[i][j-1];
if(a.now+pos[i][j]>=1)
a.now+=pos[i][j];
else
{
int dx=-pos[i][j]+1-a.now;
a.least+=dx;
a.now=1;
}
if(b.now+pos[i][j]>=1)
b.now+=pos[i][j];
else
{
int dx=-pos[i][j]+1-b.now;
b.least+=dx;
b.now=1;
}
dp[i][j]=a.least<b.least?a:b;
}
}
}
printf("%d\n",dp[n-1][m-1].least);
}
return 0;
}
上一篇:C#实现快速排序法


下一篇:C++ string