题意简述
给定两个点（即 FJ 和 Bessie）和两条路径，让这两个点沿着路径移动，求每移动一次的能量总和。
思维路径
典型的动态规划题，我们设计状态，设 \(f_{i,j}\) 表示 FJ 走到第 \(i\) 个点，Bessie 走到第 \(j\) 个点最少的能量总和。
因为他们两个都可以在某一个时间点选择走或者不走，\(f_{i,j}\) 可以由 \(f_{i-1,j-1}\) 或 \(f_{i-1,j}\) 或 \(f_{i,j-1}\) 走到，因此得到如下的转移方程式。
\[f_{i,j}=min(f_{i-1,j-1},f_{i-1,j},f_{i,j-1})+dst_{i,j}
\]
具体实现
首先我们存下路径上每一步到达的点，注意题目中的注意事项：东方向为正 X 方向，北方向为正 Y 方向。
因此，以 FJ 路径的存储方式为例，得到以下代码。
if(s[i]=='N') posf[i+1]=(node){posf[i].x,posf[i].y+1};
if(s[i]=='E') posf[i+1]=(node){posf[i].x+1,posf[i].y};
if(s[i]=='S') posf[i+1]=(node){posf[i].x,posf[i].y-1};
if(s[i]=='W') posf[i+1]=(node){posf[i].x-1,posf[i].y};
接着我们要写计算两点间距离的代码。
它们间距离的平方就等于它们横坐标之差的平方和纵坐标之差的平方的和。
代码实现如下。
ll dst(ll u,ll v){
return (posf[u].x-posb[v].x)*(posf[u].x-posb[v].x)+(posf[u].y-posb[v].y)*(posf[u].y-posb[v].y);
}
最后我们要写正式的 dp ，在预处理中要处理 \(i=0\) 和 \(j=0\) 的情况。
注意 \(i=j=0\) 时能量和为 \(0\) 而不是两个起点之间的距离。
得到预处理的代码。
f[0][0]=0;
for(ll i=1;i<=n;i++){
f[i][0]=dst(i,0)+f[i-1][0];
}
for(ll i=1;i<=m;i++){
f[0][i]=dst(0,i)+f[0][i-1];
}
AC 代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1009;
ll n,m;
struct node{
ll x,y;
} posf[N],posb[N];
ll f[N][N];
void input(){
cin>>n>>m;
cin>>posf[0].x>>posf[0].y>>posb[0].x>>posb[0].y;
string s;
cin>>s;
for(ll i=0;i<s.size();i++){
if(s[i]=='N') posf[i+1]=(node){posf[i].x,posf[i].y+1};
if(s[i]=='E') posf[i+1]=(node){posf[i].x+1,posf[i].y};
if(s[i]=='S') posf[i+1]=(node){posf[i].x,posf[i].y-1};
if(s[i]=='W') posf[i+1]=(node){posf[i].x-1,posf[i].y};
}
cin>>s;
for(ll i=0;i<s.size();i++){
if(s[i]=='N') posb[i+1]=(node){posb[i].x,posb[i].y+1};
if(s[i]=='E') posb[i+1]=(node){posb[i].x+1,posb[i].y};
if(s[i]=='S') posb[i+1]=(node){posb[i].x,posb[i].y-1};
if(s[i]=='W') posb[i+1]=(node){posb[i].x-1,posb[i].y};
// cout<<posb[i+1].x<<" "<<posb[i+1].y<<endl;
}
}
ll dst(ll u,ll v){
return (posf[u].x-posb[v].x)*(posf[u].x-posb[v].x)+(posf[u].y-posb[v].y)*(posf[u].y-posb[v].y);
}
void solve(){
f[0][0]=0;
for(ll i=1;i<=n;i++){
f[i][0]=dst(i,0)+f[i-1][0];
}
for(ll i=1;i<=m;i++){
f[0][i]=dst(0,i)+f[0][i-1];
}
for(ll i=1;i<=n;i++){
for(ll j=1;j<=m;j++){
f[i][j]=min(f[i-1][j-1],min(f[i-1][j],f[i][j-1]))+dst(i,j);
// cout<<f[i][j]<<" ";
}
// cout<<endl;
}
cout<<f[n][m];
}
int main(){
input();
solve();
return 0;
}