题目链接

P3133 Radio Contact G

思路

$dp$题

设$dp_{i,j}$为 Farmer John 走到第 i 步，Bessie 走到第 j 步需要的最小能量

很容易得到转移方程$f_{i,j}=min(f_{i-1,j},f_{i,j-1},f_{i-1,j-1})+dist$

其中$dist$为 Farmer John 在第 i 步，Bessie 在第 j 步时他们欧几里得距离的平方

即$(x_1-x_2)^2-(y_1-y_2)^2$

注意一下初始化：

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;
}

更新日志

2025/10/12 07:02

查看所有更新日志

• 7ced7-Reuploads previous blogs于 2025/10/12

版权所有

许可证：署名-非商业性-相同方式共享 4.0 国际 (CC-BY-NC-SA-4.0)