动态编程：Timus Online Judge 1119 Metro

Question

我试图在蒂姆斯在线评委上做问题http://acm.timus.ru/problem.aspx?space=1&num=1119。但是，由于某些奇怪的原因，递归函数不起作用。如果我只打印返回的最终值，则打印：“ - 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));

Answer 2

memset(dp,-1.0,sizeof dp);

此行不适用于double和float数据类型。所以不要使用memset，而是使用

  float dp[1001][1001]={0};

因此检查if(dp[x][y]!=0)return dp[x][y];我希望这是有效的。