Page 1 of 1

Communication System-pku 1018

Posted: Sat Dec 22, 2007 4:48 pm
Hello all,
I'm trying to solve this problem:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1018

This problem is here too:
http://acm.tju.edu.cn/toj/showp1258.html

but I got WA every time.
I posted it here, because I have learned many things from this forum before, but I didn't see that websites' forum active.and I really need help.
here is my code:

Code: Select all

#include<iostream>
#include<fstream>

using namespace std;

const int size=200;
struct{
int minB;
int sumP;
double r;
}S[size][size];
int main(){
ifstream cin("c.in");
int t,n,i,j,k,m[size],B[size][size],P[size][size],cursum,curmin,maxmin,maxsum;
double maxR,curR;
for(cin>>t;t>0;t--){
cin>>n;
for(i=0;i<n;i++){
cin>>m[i];
for(j=0;j<m[i];j++)
cin>>B[i][j]>>P[i][j];
if(!m[i]){i--;n--;}
}
for(i=0;i<m[0];i++){
S[0][i].minB=B[0][i];
S[0][i].sumP=P[0][i];
S[0][i].r=double(B[0][i])/double(P[0][i]);
}
for(i=1;i<n;i++){//i th device
for(j=0;j<m[i];j++){//j th factory
curmin=(S[i-1][0].minB<B[i][j])?S[i-1][0].minB:B[i][j];
cursum=S[i-1][0].sumP+P[i][j];
curR=double(curmin)/double(cursum);
maxR=curR;
maxmin=curmin;
maxsum=cursum;
for(k=1;k<m[i-1];k++){
curmin=(S[i-1][k].minB<B[i][j])?S[i-1][k].minB:B[i][j];
cursum=S[i-1][k].sumP+P[i][j];
curR=double(curmin)/double(cursum);
if(maxR<curR){
maxR=curR;
maxmin=curmin;
maxsum=cursum;
}

}//k
S[i][j].minB=maxmin;
S[i][j].sumP=maxsum;
S[i][j].r=maxR;

}//j
}//i

curmin=S[n-1][0].minB;
cursum=S[n-1][0].sumP;
curR=double(curmin)/double(cursum);
maxR=curR;
maxmin=curmin;
maxsum=cursum;
for(k=1;k<m[n-1];k++){
curmin=S[n-1][k].minB;
cursum=S[n-1][k].sumP;
curR=double(curmin)/double(cursum);
if(maxR<curR){
maxR=curR;
maxmin=curmin;
maxsum=cursum;
}
}
printf("%d   %d    %.3f\n",maxmin,maxsum,maxR);
}
return 0;
}
where is my mistake? Is it in my alghorithm or implementation?
I used DP.S[j] is the situation when we consider devices 0 to i and select the j th factory for device i.