algorithm - WA on SCUBADIV spoj

Question

我正在尝试解决 http://www.spoj.pl/problems/SCUBADIV/ spoj.com 上的这个问题，但我得到了 WA。我写了一个递归解决方案并使用了内存。谁能帮我找出我的错误？提前致谢:)

int oxygen[1010],nitrogen[1010],weight[1010],n;
int dp[200][200];
// oxy is the amnt of oxygen needed , nitro is the amnt of nitrogen needed , pos     denotes element picked up till now
int calculate (int oxy , int nitro ,int pos){

long long int min = 10000000;
if(oxy <=0 && nitro <=0)
    return 0;
if(dp[oxy+79][nitro+21]!=-1)    
    return dp[oxy+79][nitro+21];
else{
    for(int i=pos+1;i<n;i++){

            int val = calculate (oxy - oxygen[i] ,nitro - nitrogen[i] , i)+ weight[i];

            if(val<min){
                min = val;
            }
        }
    }
    dp[oxy+79][nitro+21]=min;
    return min;

}   

int main(){
int test;
int i,oxy,nitro;
cin>>test;
while(test--){
    cin>>oxy>>nitro;
    cin>>n;
    for( i=0;i<n;i++){
        cin>>oxygen[i]>>nitrogen[i]>>weight[i];
    }
    for(i=0;i<110;i++){
        for(int j=0;j<110;j++){
            dp[i][j]=-1;
        }
    }   

    long long int min =1000000; 
    for(i=0;i<n;i++){
        int val = calculate(oxy-oxygen[i],nitro-nitrogen[i], i)+weight[i];
        if(val<min)
            min = val;
    }

    cout<<min<<endl;
}

return 0;
}

正如指出的那样，我查看并发现我读取了错误的氧气和氮气约束。我针对该约束修改了我的代码，但它仍然给出了错误的答案

int oxygen[1010],nitrogen[1010],weight[1010],n;
int dp[900][900];
// oxy is the amnt of oxygen needed , nitro is the amnt of nitrogen needed , pos denotes element picked up till now
int calculate (int oxy , int nitro ,int pos){

long long int min = 800000;
if(oxy <=0 && nitro <=0)
    return 0;
if(dp[oxy+800][nitro+100]!=-1)  
    return dp[oxy+800][nitro+100];
else{
    for(int i=pos+1;i<n;i++){

            int val = calculate (oxy - oxygen[i],nitro - nitrogen[i] , i)+ weight[i];

            if(val<min){
                min = val;
            }
        }
    }
    dp[oxy+800][nitro+100]=min;
    return min;

}   

int main(){
int test;
int i,oxy,nitro;
cin>>test;
while(test--){
    cin>>oxy>>nitro;
    cin>>n;
    for( i=0;i<n;i++){
        cin>>oxygen[i]>>nitrogen[i]>>weight[i];
    }
    for(i=0;i<100+800;i++){
        for(int j=0;j<800+100;j++){
            dp[i][j]=-1;
        }
    }   
//cout<<"here";
    long long int min =800000;  
    for(i=0;i<n;i++){
        int val = calculate(oxy-oxygen[i],nitro-nitrogen[i], i)+weight[i];
        if(val<min)
            min = val;
    }

    cout<<min<<endl;
}

return 0;
}

Answer 1

我相信你的代码outputs 119 (实际上我时常遇到运行时错误)在这个测试用例上:

1
22 175
5
3 36 120
10 25 129
5 50 250
1 45 130
4 20 119

虽然这显然不是正确答案。希望这可以帮助。