1
我正試圖在spoj.com上解決http://www.spoj.pl/problems/SCUBADIV/這個問題但是我得到了WA。我寫了一個遞歸解決方案並使用記憶。 任何人都可以幫我找到我的錯誤嗎？感謝提前:)WA在SCUBADIV上spoj
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;
}
正如指出，我看了一下，發現我讀的氧和氮的錯誤限制..我modoified我的代碼爲約束還是它給出錯誤的答案
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;
}