Разный выход с возвратом и DP - PullRequest
Новая
       0

Разный выход с возвратом и DP

0 голосов
/ 14 мая 2018

Я использую DP для решения проблемы, но решение без DP, т. Е. Просто обратное отслеживание, дает правильный вывод, в то время как тот же код только с DP дает неправильный вывод. Не могу понять, почему.

ссылка на вопрос- https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1278

Вот код: 

#include<bits/stdc++.h>
using namespace std;
typedef long long int lli;
#define oo 1000000007;
lli dp[12][1005];
int a[10][1005];
int n;
lli calc(int alt,int i){
    if(dp[alt][i] != -1) {
        return dp[alt][i];
    }
    if(i==n && alt==0) {
        return 0;
    }
    if(alt>9 || alt<0 || i==n) {
        return oo;
    }
    return dp[alt][i] = min(
        min(
            lli(30) - a[alt][i] + calc(alt  ,i+1),
            lli(20) - a[alt][i] + calc(alt-1,i+1)
        ),
        lli(60) - a[alt][i] + calc(alt+1,i+1)
    );
}
int main(){
    int t;
    string bl;
    scanf("%d",&t);
    while(t--){
        getline(cin,bl);
        memset(dp,-1,sizeof dp);
        scanf("%d",&n);
        n = n/100;
        for(int i=9; i>=0; i--) {
            for(int j=0; j<n; j++) {
                scanf("%d",&a[i][j]);
            }
        }
        lli ans = calc(0,0);
        printf("%lld\n",ans);
        if(t!=0) printf("\n");
    }
}

вход 

1
400
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 9 9 1
1 -9 -9 1

Правильный вывод 120.

1 Ответ

0 голосов
/ 14 мая 2018 
if(dp[alt][i] != -1) {
    return dp[alt][i];
}

lli(20) - a[alt][i] + calc(alt-1,i+1)

Вам просто (не) повезло, что программа не вызвала сбой!

Для alt == -1 вы читаете только какой-то случайный мусор в рекурсии. Вы читаете случайные значения из массива dp.

Переключите их так, и это должно работать (или, по крайней мере, иметь определенное поведение): 

if(i==n && alt==0) {
    return 0;
}
if(alt>9 || alt<0 || i==n) {
    return oo;
}
if(dp[alt][i] != -1) {
    return dp[alt][i];
}

В любом случае, ваш подход просто не работает. Сначала вы проходите глубину (находит какой-либо путь!), Но порядок обхода сначала должен быть широким, чтобы найти кратчайший маршрут.

Это означает, что вы не можете использовать рекурсию, подобную этой, но вместо этого должны выполнять итерацию по alt во внутреннем и i во внешнем цикле. Затем вы можете заполнить поле пути шаг за шагом.

Такое наивное динамическое программирование - не лучшее решение для этой задачи. Вам лучше относиться к нему как к ориентированному взвешенному графу и применять стандартную Дейкстру. С помощью вашего метода вы рассчитаете (без необходимости) все возможные маршруты.

...