c++ - WA in scubadiv spoj(自上而下的 dp)

Question

我卡在 this question 上了得到WA。

我见过很多关于这个问题的自下而上的实现。我的自上而下的实现不适用于内存，但没有它也能正常工作。我该如何纠正它？

#include<cstdio>
#include<cstring>
#include<iostream>

#define INF 0x7FFFFFFF

using namespace std;

int o,n,num,ox[2000],nt[2000],wt[2000];
int dp[2000][2000];

int dive(int index,int oxygen,int nitrogen,int weight) {
    if(dp[oxygen][nitrogen]!=-1) return dp[oxygen][nitrogen];
    int &ret=dp[oxygen][nitrogen];
    if(oxygen>=o&&nitrogen>=n) {
        ret=weight; 
        return ret;
    }
    if(index==num) {
        ret=INF;
        return ret;
    }
    ret= min(dive(index+1,oxygen+ox[index],nitrogen+nt[index],weight+wt[index]),dive(index+1,oxygen,nitrogen,weight));  
    return ret;
}

main() {
    int c;
    scanf("%d",&c);
    while(c--) {
        memset(dp,-1,sizeof(dp));
        scanf("%d%d",&o,&n);
        scanf("%d",&num);
        for(int i=0;i<num;++i) {
            scanf("%d%d%d",&ox[i],&nt[i],&wt[i]);
        }
        printf("%d\n",dive(0,0,0,0));
    }
    return 0;
}

Answer 1

试试这个测试:

1
21 79
5
1 1 800
1 1 800
1 1 800
1 1 800
17 75 800

在我看来正确答案应该是 800 * 5 = 4000 对吗？你的程序输出 something else .