1
나는 http://www.spoj.pl/problems/SCUBADIV/이 질문을 spoj.com에서 해결하려고하지만 WA가 나타납니다. 나는 재귀 적 해법을 작성하고 암기를 사용했다. 누군가 내 실수를 찾도록 도와 줄 수 있습니까? 여전히 잘못된 답을 준다 내가 그 제약 조건 내 코드를 modoified .. 미리 :) 감사드립니다WA on 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;
}
지적 내가 보니 내가 산소와 질소에 대한 잘못된 제약을 읽어 발견
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;
}