OI题解 - DesertWind[Topcoder 1570]

之前做的一道DP题,现在才写
DP题做的有点多了……


『题意』

>> There!
有一个 $r\times c$ 的平面,你在上面”@”的位置,平面上有一些屏障”X”,不能通过,你需要到达平面上的一个绿洲”*“。
你可以向你周围八连通的位置移动(除非是屏障)。平面上会刮风,你直到要决定下一步怎么走时才会知道会向哪边刮风(风向可以是 左、右、上、下、左上、右下、左下、右上),如果你行走的方向与风向恰好相反,将会花费 $3$ 点体力,否则花费 $1$ 点体力。
求在最坏情况下,到达绿洲的最少体力花费。如果不能到达绿洲,输出 $-1$。


『解析』

题意非常混乱……但我们可以知道最坏情况下,风向一定是向你当前位置到达绿洲的最短路径的下一个位置吹的(反证可得:如果风向不往最短路径反方向吹,那么你走最短路径方向一定是最优的,最坏情况下风会尽量让你的花费最大,所以它一定会破坏最短路径)。
如果我们考虑从起点出发到一个点的最小花费,由于我们不知道风会怎么吹,而且会产生后效性,就无法DP;那么我们更改状态——dp[i][j] 表示从 $(i,j)$ 到达绿洲的最小花费,这样倒过来想,我们可以知道在 $(i,j)$ 时风向会怎么吹(前面证明了风会往最短路径反方向吹)。那么就容易想到转移方程,假设当前在 $(a,b)$ 下一步要走到 $(c,d)$ :

令 $fir$ 表示 dp[c][d] 的最小值,$sec$ 表示 dp[c][d] 的次小值;
则 dp[i][j]=min(fir+3,sec+1)

数据规模不大,暴力枚举转移就行了。


『源代码』

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/*Lucky_Glass*/
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
typedef long long ll;
const int N=50;
const ll INF=(1ll<<60);
const int dir[8][2]={{0,1},{1,0},{0,-1},{-1,0},{1,-1},{-1,1},{-1,-1},{1,1}};
class DesertWind{
public:
ll dp[N+7][N+7];
int ROL,COL,BEGINx,BEGINy;
ll daysNeeded(vector<string> maz){
ROL=maz.size();COL=maz[0].length();
for(int i=0;i<ROL;i++)
for(int j=0;j<COL;j++){
dp[i][j]=INF;
if(maz[i][j]=='@') BEGINx=i,BEGINy=j;
if(maz[i][j]=='*') dp[i][j]=0;
}
for(int QwQ=0;QwQ<ROL*COL;QwQ++){
for(int i=0;i<ROL;i++)
for(int j=0;j<COL;j++){
if(maz[i][j]=='X') continue;
ll fir=INF,sec=INF;
for(int k=0;k<8;k++){
int I=i+dir[k][0],J=j+dir[k][1];
if(I<0 || I>=ROL || J<0 || J>=COL) continue;
if(fir>dp[I][J]) sec=fir,fir=dp[I][J];
else if(sec>dp[I][J]) sec=dp[I][J];
}
if(fir!=INF) dp[i][j]=min(dp[i][j],fir+3);
if(sec!=INF) dp[i][j]=min(dp[i][j],sec+1);
}
}
return dp[BEGINx][BEGINy]==INF? -1:dp[BEGINx][BEGINy];
}
};

The End

Thanks for reading!

Email: lucky_glass@foxmail.com ,欢迎提问~

0%