10086 - Test the Rods

[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;
}

[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!

[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 :*

[crip121]

its a DP problem...

[@li_kuet]

What is wrong with my code ??
Any tricky case ??
Help please ...

Code: Select all

AC
Made an stupid mistake :P

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

[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;
}

[brianfry713]

return 0;

[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.

[brianfry713]

Try changing int m[25] to int m[30]

[bradd123]

It worked for RE Error. But Now I am getting Time LImit Exceeded. How to improve this solution.

[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.