DARPA 문제를 DP로 풀어보고 있는데 질문 드립니다..

  • User Avatar
    skan1543

    [[problem:DARPA]]

    #include<stdio.h>
#include<algorithm>
using namespace std;

#define MIN -987654321

int N, M;
double cache[301][301];
double p[305] = { 0, };

double calc(int point, int count)
{
    if (count == 1) return 0;
    if (cache[point][count] != 0.0) return cache[point][count];
    
    double max = MIN;

    for (int i = point-1; i >= count-2; i--)
    {
        double tmp = calc(i,count - 1);
        if (tmp > p[point] - p[i] || tmp==0) tmp = p[point] - p[i];
        if (max < tmp) max = tmp;
    }
    return cache[point][count] = max;
}

int main()
{
    int T;
    scanf("%d", &T);
    while (T--)
    {
        scanf("%d %d", &M, &N);
        for (int i = 0; i < N; i++)
        {
            for (int j =0; j <=M; j++) cache[i][j] = 0.0;
            scanf("%lf", &p[i]);
        }
        printf("%.2lf\n", calc(N - 1, M));
    }
    return 0;
}

    D[i][j] =i개까지의 정류소? 를 써서 .. 카메라를 j개 달았을때의 최대값 = max( min(D[i-1][j-1],point[i]-point[i-1]),
    min(D[i-2][j-1],point[i]-point[i-2]),
    min(D[i-3][j-1],point[i]-point[i-3]),...,)

    점화식을 위처럼 세워서 풀었는데 계속 WA에 부딪히네요..

    구글에서 책에있는 이분법을 구현한 코드를 갖고

    데이터를 난수를 생성해 답을 비교해봐도, 제 것이 오래걸리면 오래걸려도 답은 똑같이 뜨는데 말입니다 ㅠㅠ

    왜 WA가 뜨는 걸까요...?


    10년 전
1개의 댓글이 있습니다.
  • User Avatar
    hyunhwan

    문제는 최대값의 최소를 찾는 것인데 해당 해법의 경우에는 직전에 찾았던 최대값과 현재 가능한 최대값 중 큰것을 취하는 식으로 dp가 설계되어있는것 같습니다. 이야기하신 점화식과는 일치하지 않아보입니다.


    10년 전 link

  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.