글 읽기 - 경찰차문제 최소비용

zmfldlwl 6년 전 0

dp식에 뭔가 허점이 있는거 같은데

ㅠㅠ 일단 경로뽑기 이전에 최소값부터 뽑아보려고 하는데 계속 중간에 틀리네요

2차원 dp가 의미하는게

dp[1번째경찰차가 처리한 사건 수][2번째경찰차가 처리한 사건수] = 일때 최소경로 값

을 가지고 있도록 구현했는데 틀리네요 도대체 반례가 어떨때 발생할지 알려주세요!

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>

#define MAX 2100000000

using namespace std;

class Point
{
public:
    int x;
    int y;
    Point() : x(0), y(0) {}
    Point(int x, int y) : x(x), y(y){}
};

//dp로 가지치기
int dp[1005][1005];
//경로 기록
int res[1005];
int res_count;

int n, m;
Point arr[1005];

int r_min = MAX;

int my_abs(int a)
{
    if (a < 0)
        return a * -1;
    else
        return a;
}

int get_distance(Point a, Point b)
{
    int res = 0;

    res = my_abs(a.x - b.x) + my_abs(a.y - b.y);

    return res;
}

int my_min(int a, int b)
{
    return a > b ? b : a;
}

void REQ(Point police1, Point police2, int a, int a1, int b)
{
    if ((a + a1) > m)
    {
        return;
    }

    if (dp[a][a1] != MAX && dp[a][a1] < b)
        return;

    dp[a][a1] = b;

    //1번 위치 경찰차가 처리
    REQ(arr[a + a1], police2, a + 1, a1, b + get_distance(police1, arr[a + a1]));

    //2번 위치 경찰차가 처리
    REQ(police1, arr[a + a1], a, a1 + 1, b + get_distance(police2, arr[a + a1]));

    return;
}

int main()
{
    cin >> n >> m;

    for (int i = 0; i < 1005; i++)
        for (int j = 0; j < 1005;j++)
            dp[i][j] = MAX;

    for (int i = 0; i < m; i++)
        cin >> arr[i].x >> arr[i].y;

    //시작 경찰차는 (1,1), (n,n)에 위치한다.

    //경찰차 위치, 경찰차 마다 사건처리 개수, 누적길이
    REQ(Point(1, 1), Point(n, n), 0, 0, 0);

    for (int i = 0; i <= m; i++)
        r_min = my_min(r_min, dp[i][m - i]);
    
    cout << r_min << endl;

    return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

경찰차문제 최소비용

zmfldlwl 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말