UVa OJ Board

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

Code: Select all

AC
Made an stupid mistake :P

Code: Select all

5 0
1
5
10 20 30 20 50
40 25 10 50 20

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