c++ - 动态规划 : Timus Online Judge 1119 Metro

Question

我正在尝试做题http://acm.timus.ru/problem.aspx?space=1&num=1119在 Timus Online Judge 上。但是，由于某些奇怪的原因，递归函数不起作用。如果我只打印返回的最终值，它会打印:“-nan”。当我打印它的四舍五入形式时，它打印出一个垃圾值。

#include <iostream>
#include <cstring>
#include <cmath>
#define min(x,y) ((x<y) ? (x) : (y))
using namespace std;
int x,y;
float dp[1001][1001];    //for memoization
bool d[1001][1001];      // for storing whether diagonal movement is possible or not
float solve(int x,int y) {
    if (dp[x][y]!= -1.0)
        return dp[x][y];
    if (x == 0 && y == 0)
        return (dp[x][y] = 0.0);
    if (x == 0 )
        return (dp[x][y] = y*100);
    if (y == 0)
        return (dp[x][y] = x*100);
    float ret;
    float r1,r2,r3;
    r1 = 100.0 + solve(x-1,y);
    r2 = 100.0 + solve(x,y-1);
    ret = min(r1,r2);
    if (d[x][y]) {
        r3 = solve(x-1,y-1);
        r3 = r3 + 141.42;
        ret = min(ret,r3);
    }
    dp[x][y] = ret;
    return ret;
}
int main() {
    cin >> x >> y;
    int k;
    int d1,d2;
    cin >> k;
    memset(dp,-1.0,sizeof dp);
    memset(d,false,sizeof d);
    for (int i=0;i<k;i++) {
        cin >> d1 >> d2;
        d[d1][d2]=true;
    }
    float dist = solve(x,y);
    int ans = dist;
    if (dist - ans > 0.5) {
        ans++;
    }
    cout << ans << endl;    // Prints a garbage value
}                           // cout << dist << endl prints "-nan"

这是 ideone 链接:http://ideone.com/6C2WjR

Answer 1

memset(dp,-1.0,sizeof dp); 没有按照你的想法去做，使用 std::fill 或 std::fill_n 代替。

或者只是一个std::vector:

std::vector<std::vector<float>> dp(1001, std::vector<float>(1001, -1.f));