결국 이 문제는 변수가 아래 두가지인 셈이다.
1. 현재위치와 다음위치 사이의 거리
2. 다음위치의 매력도
이 문제를 해결하기위해 생각해 본 것이 한가지 변수를 고정시키면 어떻게 풀 수 있는가 였다.
현재 위치에서 가장 먼 점이라는 것은 다음위치로 갈수있는 점들 중 4모서리에 가장 가까운 네점중 하나가 우리가 원하는 최적해가 된다는 뜻이다.
2번 변수가 고정되어있지 않고 변한다고 해도, 이를 이용해 DP로 접근하면 답을 구할수 있다.
#include <stdio.h>
#include <vector>
#define ll long long
using namespace std;
struct st {
int r, c, idx; ll val, sum;
};
struct st2 {
int r, c, idx, val;
};
vector <st> vec[1000001];
st2 dat[1001][1001];
ll d[1001][1001] = { 0 };
int sign[4][2] = { 1,1,-1,1,1,-1,-1,-1 };
__inline ll max(ll a, ll b) {
return a > b ? a : b;
}
__inline ll ab(ll n) {
return n > 0 ? n : -n;
}
int main() {
int start = 1000000;
int end=0;
int n, m; scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
scanf("%d", &dat[i][j].idx);
dat[i][j].r = i;
dat[i][j].c = j;
if (dat[i][j].idx!=0 && dat[i][j].idx < start) start = dat[i][j].idx;
if (dat[i][j].idx > end) end = dat[i][j].idx;
}
}
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
scanf("%d", &dat[i][j].val);
st tmp;
tmp.r = dat[i][j].r;
tmp.c = dat[i][j].c;
tmp.val = dat[i][j].val;
tmp.idx = dat[i][j].idx;
vec[dat[i][j].idx].push_back(tmp);
}
}
st cand[4] = { 0 };
for (int i = 0; i < 4; i++) cand[i].sum = -987654321;
int last;
//dp시작
for (int j = start; j <= end; j++) {
if (vec[j].size() == 0) continue;
last = j;
//후보들로 d배열 갱신
for (int i = 0; i < vec[j].size(); i++)
{
int n_r = vec[j][i].r;
int n_c = vec[j][i].c;
for (int k = 0; k < 4; k++)
{
int r = cand[k].r;
int c = cand[k].c;
if (r == 0 || c == 0) continue;
ll v = cand[k].val;
d[n_r][n_c] = max(d[n_r][n_c], ab(n_r - r) + ab(n_c - c) + v);
}
d[n_r][n_c] += (ll)dat[n_r][n_c].val;
}
for (int i = 0; i < vec[j].size(); i++) {
//후보갱신
int r = vec[j][i].r;
int c = vec[j][i].c;
ll v = d[r][c];
ll s;
for (int k = 0; k < 4; k++) {
s = sign[k][0] * r + sign[k][1] * c + v;
if (s > cand[k].sum) {
cand[k].sum = s;
cand[k].r = r;
cand[k].c = c;
cand[k].val = v;
}
}
}
}
ll ans = 0;
for (int i = 0; i < vec[last].size(); i++) ans = max(ans, d[vec[last][i].r][vec[last][i].c]);
printf("%lld", ans);
}