You are not logged in. Please login at www.codechef.com to post your questions!

×

FEEDING MINIONS INOI PRACTICE SERVER

I have attached my code for feeding minions (i have used memoization).

I am getting a big zero.

please find errors.

#include<iostream>
 #include<algorithm>
#include<fstream>
 #define F(aa,bb,cc) for(int aa=bb;aa<cc;++aa)
 using namespace std;
 int t,n;long long int a[1005],b[1005],c[1005],ans[55],tab[1005][4];
 bool mark[1005];
long long int dp(int pos,int gen)

 {

   if(!pos)
     {
    if(gen==1)
    return a[pos];
    return b[pos];
     }
long long int val;
if(gen==1)
{
    mark[pos]=1;
    if(tab[pos][1])
    return tab[pos][1];
    val=a[pos];
    val+=max(dp(pos-1,2),dp(pos-1,3));
            tab[pos][1]=val;
}
else if(gen==2)
{
     if(tab[pos][2])
    return tab[pos][2];
    val=b[pos];
    if(pos==n-1)
    {
        mark[pos]=0;
       val+=max(dp(pos-1,2),dp(pos-1,1));
    }

    else
    {
        if(!mark[pos+1])
        {
            mark[pos]=0;
            val+=max(dp(pos-1,1),dp(pos-1,2));
        }
        else
        {
            mark[pos]=1;
            val+=max(dp(pos-1,2),dp(pos-1,3));
        }
    }
    tab[pos][2]=val;
}
else
{
    mark[pos]=0;
     if(tab[pos][3])
    return tab[pos][3];
    val=c[pos];
    val+=max(dp(pos-1,2),dp(pos-1,1));
    tab[pos][3]=val;
}
return val;

}

int main() {

cin>>t;
F(tt,0,t)
{
    cin>>n;
    F(i,0,n) cin>>a[i]>>b[i]>>c[i];
    ans[tt]=max(dp(n-1,1),dp(n-1,2));
    F(i,0,n)
    F(j,1,4)
    tab[i][j]=0;
    F(i,0,n)
    mark[i]=0;
}
F(tt,0,t) cout<<ans[tt]<<endl;
return 0;

}

asked 25 Jan '15, 17:48

a1a99_3's gravatar image

6★a1a99_3
6113
accept rate: 16%

Can you explain your DP equation?

(26 Jan '15, 09:38) ketanhwr6★

@ketanhwr

dp(i,1)---> max.joy of the minions 0 to i where ith minion is fed before both its neighbors.

similarly, dp(i,2)---> when minion i is fed before one of its neighbor. dp(i,3)---> when minion i is fed after both its neighbors.

(26 Jan '15, 22:49) a1a99_36★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×1,790
×104

question asked: 25 Jan '15, 17:48

question was seen: 603 times

last updated: 26 Jan '15, 22:49