Page 1 of 1
10086 - Test the Rods
Posted: Thu Oct 03, 2002 1:55 pm
by Andrey Popyk
Code: Select all
#include <iostream.h>
#define DIM 307
#define oo 2000000000L
long N,T1,T2;
long A[307];
int B[33][DIM],C[33][DIM];
long D[33][DIM];
int R[33][DIM];
int Res[33];
int ReadData()
{ long i,j;
cin>>T1>>T2;
if(T1==0 && T2==0) return 0;
cin>>N;
for(i=1;i<=N;i++)
{
cin>>A[i];
for(j=1;j<=A[i];j++) cin>>B[i][j];
for(j=1;j<=A[i];j++) cin>>C[i][j];
}
return 1;
}
void Solve()
{ long s,k,p,i,j;
for(i=0;i<33;i++)
for(j=0;j<DIM;j++) D[i][j]=0;
s=0;
for(i=1;i<=N;i++)
{ s+=A[i];
for(j=0;j<=T1;j++)
{ D[i][j]=oo;
p=j; if(A[i]<j) p=A[i];
for(k=0;k<=p;k++)
if(D[i][j]>D[i-1][j-k]+B[i][k]+C[i][A[i]-k])
{
D[i][j] = D[i-1][j-k]+B[i][k]+C[i][A[i]-k];
R[i][j] = k;
}
}
}
cout<<D[N][T1]<<endl;
p=T1;
for(i=N;i>=1;i--)
{ Res[i]=R[i][p];
p=p-R[i][p];
}
for(i=1;i<=N;i++) cout<<Res[i]<<' ';
cout<<endl<<endl;
}
int main()
{
while(ReadData()) Solve();
return 0;
}
Posted: Wed Nov 27, 2002 9:32 am
by zyc
for(k=0;k<=p;k++)
need another condition k<=a[1]+a[2]+...+a[i-1]
if you add it , it is ok!
Re: 10086 - Test the Rods
Posted: Fri Oct 08, 2010 7:03 pm
by Angeh
HI alll could somebody help me ...
whats The underlying algorithm ...
how to solve this problem ...
i'll be glad if any one could help ....
Thanks :*
Re: 10086 - Test the Rods
Posted: Thu Oct 14, 2010 12:38 am
by crip121
its a DP problem...
Re: 10086 - Test the Rods
Posted: Tue Feb 11, 2014 10:46 pm
by @li_kuet
What is wrong with my code ??
Any tricky case ??
Help please ...
Can try this input who r getting WA
Code: Select all
5 0
1
5
10 20 30 20 50
40 25 10 50 20
Output : 50
Re: 10086 - Test the Rods
Posted: Wed Feb 18, 2015 11:02 am
by bradd123
Hi, Can anyone tell me why my code shows RE for this problem.
Code: Select all
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define INF 2000000000
int T1,T2,n;
int m[25];int C[50][50][2];
int memo[50][310][310];
int trace[50][310][310];
int TesttheRods(int idx,int rem1,int rem2){
if(idx>=n){
if(rem1==0&&rem2==0) return 0;
else return INF;
}
if(rem1==0&&rem2==0) return INF;
if(rem1<0||rem2<0) return INF;
if(memo[idx][rem1][rem2]!=-1) return memo[idx][rem1][rem2];
int tmp=INF;
for(int i=0;i<=m[idx];i++){
int j=m[idx]-i;
int sum1=0,sum2=0;
if(i==0) sum1=0;
else sum1=C[idx][i-1][0];
if(j==0) sum2=0;
else sum2=C[idx][j-1][1];
int tmpvalue=((TesttheRods(idx+1,rem1-i,rem2-j))+sum1+sum2);
if(tmpvalue<tmp){
tmp=tmpvalue;
trace[idx][rem1][rem2]=i;
}
}
return memo[idx][rem1][rem2]=tmp;
}
int main()
{
//freopen("in.txt","r",stdin);
while(scanf("%d %d",&T1,&T2)){
if(T1==0&&T2==0) break;
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d",&m[i]);
for(int j=0;j<m[i];j++) scanf("%d",&C[i][j][0]);
for(int j=0;j<m[i];j++) scanf("%d",&C[i][j][1]);
}
memset(memo,-1,sizeof memo);
memset(trace,-1,sizeof trace);
int val=TesttheRods(0,T1,T2);
printf("%d\n",val);
printf("%d",trace[0][T1][T2]);
int ind1=trace[0][T1][T2];
int ind2=m[0]-ind1;
int total1=T1,total2=T2;
for(int i=1;i<n;i++){
total1-=ind1;total2-=ind2;
ind1=trace[i][total1][total2];
ind2=m[i]-ind1;
printf(" %d",ind1);
}
printf("\n");
printf("\n");
}
return 0;
}
Re: 10086 - Test the Rods
Posted: Wed Feb 18, 2015 9:30 pm
by brianfry713
return 0;
Re: 10086 - Test the Rods
Posted: Thu Feb 19, 2015 2:12 pm
by bradd123
@Brianfry713 : I added return 0; to the program Still It shows RE. Could you please tell me any other mistakes. I think it is out of bounds error. But I couldn't find it. Please Give me some test cases.
Re: 10086 - Test the Rods
Posted: Thu Feb 19, 2015 10:58 pm
by brianfry713
Try changing int m[25] to int m[30]
Re: 10086 - Test the Rods
Posted: Fri Feb 20, 2015 11:46 am
by bradd123
It worked for RE Error. But Now I am getting Time LImit Exceeded. How to improve this solution.
Re: 10086 - Test the Rods
Posted: Wed Feb 25, 2015 10:33 pm
by brianfry713
My algorithm AC in 0.072 seconds.
My variables:
int m[30];
int m_sum[31]; //m_sum[0] is always 0.
int C[30][21][2]; //C[x][0][y] is always 0. I use x and y here to mean any valid integer
int dp[31][301]; //dp[j] is the minimum cost to build a total of j rods at NCPC after considering site i.
int p[31][301]; //each time you update dp[j], p[j] = k indicates that dp[k] was used. This is needed for the second line of the output.
Read the input, calculate m_sum.
Initialize the relevant parts of dp to infinity, dp[0][0] equals 0.
Iterate through each site, considering each relevant part of the dp array filled after the previous site, and each of the relevant m + 1 possibilities for this site.
The first line of the answer is at dp[n][T1], the second line is printed by backtracking through p.