알얼알/0514

dp[i][j] : i번째 단계에 j번째 칸에 도착하는 경우의 최대값

dp[i][1] = MAX(dp[i-1][1], dp[i-1][2]) + val[i][1]
dp[i][2] = MAX(dp[i-1][1], dp[i-1][2], dp[i-1][3]) + val[i][2]
dp[i][3] = MAX(dp[i-1][2], dp[i-1][3]) + val[i][3]

최소값은 MAX를 MIN으로 바꾸고 똑같이 하면 됨.

#include <iostream>
#define MAX(x,y) ((x)>(y)?(x):(y))
#define MIN(x,y) ((x)<(y)?(x):(y))
#define MAX3(x,y,z) MAX(MAX(x,y),z)
#define MIN3(x,y,z) MIN(MIN(x,y),z)
using namespace std;

int arr[100001][4];
int dp[100001][4][2];

int main() {
  int N;
  cin >> N;

  for (int i = 1; i <= N; i++)
    cin >> arr[i][1] >> arr[i][2] >> arr[i][3];

  for (int i = 1; i <= N; i++) {
    dp[i][1][0] = MIN(dp[i-1][1][0], dp[i-1][2][0]) + arr[i][1];
    dp[i][2][0] = MIN3(dp[i-1][1][0], dp[i-1][2][0], dp[i-1][3][0]) + arr[i][2];
    dp[i][3][0] = MIN(dp[i-1][2][0], dp[i-1][3][0]) + arr[i][3];
    dp[i][1][1] = MAX(dp[i-1][1][1], dp[i-1][2][1]) + arr[i][1];
    dp[i][2][1] = MAX3(dp[i-1][1][1], dp[i-1][2][1], dp[i-1][3][1]) + arr[i][2];
    dp[i][3][1] = MAX(dp[i-1][2][1], dp[i-1][3][1]) + arr[i][3];
  }

  cout << MAX3(dp[N][1][1], dp[N][2][1], dp[N][3][1]) << ' ';
  cout << MIN3(dp[N][1][0], dp[N][2][0], dp[N][3][0]);
  return 0;
}

for _ in range(int(input())):
  m,n,x,y=map(int,input().split())
  if not (1<=x<=m and 1<=y<=n):
    print(-1)
    continue

  if m<n:
    m,n=n,m
    x,y=y,x

  i=x
  if x<=n:
    j=x
  else:
    j=(x-1)%n+1

  ans,first_j=i,j
  while i-j!=x-y:
    j+=m-n
    if j>n:
      j=(j-1)%n+1
    if j==first_j:
      ans=-1
      break
    ans+=m

  print(ans)