之前做的一道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
|
#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 ，欢迎提问~