Radio Contact G
题目链接
思路
题
设为 Farmer John 走到第 i 步，Bessie 走到第 j 步需要的最小能量
很容易得到转移方程
其中为 Farmer John 在第 i 步，Bessie 在第 j 步时他们欧几里得距离的平方
即
注意一下初始化：
f[i][0] = f[i - 1][0] + dist;
f[0][i] = f[i - 1][0] + dist;
f[0][0] = 0; //初始位置不消耗能量然后这道题就愉快的 AC 了
代码
#include<cstdio>
#include<cstring>
#define fo(i,x,y) for(register int i=x;i<=y;++i)
#define go(i,x,y) for(register int i=x;i>=y;--i)
#define INF 0x3f3f3f3f
#define il inline
#define ll long long
#define ull unsigned long long
using namespace std;
const int N = 1005;
int n, m, fx, fy, bx, by;
char fs[N], bs[N];
int f[N][N];
il int min(const int &a, const int &b) {return a < b ? a : b;}
il void move(int &x, int &y, const char &t) {
switch(t) {
case 'N': ++y; break;
case 'S': --y; break;
case 'E': ++x; break;
case 'W': --x; break;
}
}
il int dist(const int &x1, const int &y1, const int &x2, const int &y2) {
return (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
}
int main() {
scanf("%d%d%d%d%d%d%s%s", &n, &m, &fx, &fy, &bx, &by, fs + 1, bs + 1);
int lenf = strlen(fs + 1), lenb = strlen(bs + 1);
int tx1 = fx, ty1 = fy, tx2 = bx, ty2 = by;
fo(i, 1, lenf) {
move(tx1, ty1, fs[i]);
f[i][0] = f[i - 1][0] + dist(tx1, ty1, bx, by);
}
fo(i, 1, lenb) {
move(tx2, ty2, bs[i]);
f[0][i] = f[0][i - 1] + dist(fx, fy, tx2, ty2);
}//初始化
tx1 = fx, ty1 = fy;
fo(i, 1, lenf) {
tx2 = bx, ty2 = by;
move(tx1, ty1, fs[i]);
fo(j, 1, lenb) {
move(tx2, ty2, bs[j]);
f[i][j] = min(f[i - 1][j], min(f[i][j - 1], f[i - 1][j - 1])) + dist(tx1, ty1, tx2, ty2);
}
}
printf("%lld\n", f[lenf][lenb]);
return 0;
}