Hi guys I am trying to solve MENU problem on SPOJ.
I used a dp state which contains (rem_days,rem_budget,prev_dish,cnt_prev_dish)
Any one tell me where I am getting wrong or some other logic.
#include<cstdio>
#include<iostream>
#include<cstring>
#define INF 1000000000
using namespace std;
int k,n,m;
long long dp[51][150][51][51],mm[51][150][51];
int c[51],v[51],pr=-1;
long long solve(int k,int B,int prev,int cnt)
{
if(B<0)return -INF;
if(B==0 and k>0)return -INF;
if(k==0)return 0;
if(dp[k][B][prev][cnt]!=-1)return dp[k][B][prev][cnt];
long long ans=-INF,idx=-1;
for(int i=0;i<n;i++)
{
if(prev!=i)
{
int tmp=solve(k-1,B-c[i],i,1);
if(tmp!=-INF)
{
if(tmp+v[i]>ans)
{
ans=tmp+v[i];
idx=i;
}
else if(tmp+v[i]==ans)
{
if((v[i]-c[i])>(v[idx]-c[idx]))
idx=i;
}
}
}
else
{
int val=v[i]/2;
if(cnt>1)val=0;
int tmp=solve(k-1,B-c[i],i,cnt+1);
if(tmp!=-INF)
{
if(tmp+val>ans)
{
ans=tmp+val;
idx=i;
}
}
}
}
mm[k][B][prev]=idx;
pr=idx;
return dp[k][B][prev][cnt]=ans;
}
void recurse(int k,int B,int pre)
{
if(k==0)return;
else
{
int x=mm[k][B][pre];
recurse(k-1,B-c[x],x);
cout<<x+1<<" ";
}
}
int main()
{
cin>>k>>n>>m;
while(k|n|m)
{
memset(dp,-1,sizeof dp);
memset(mm,-1,sizeof mm);
long long ans=-INF;
for(int i=0;i<n;i++)
{
cin>>c[i]>>v[i];
v[i]<<=1;
}
double x=solve(k,m,-1,0);
if(x<=0)
cout<<"0.0"<<endl;
else
{
printf("%.1lf\n",x/2);
recurse(k-1,m-c[pr],pr);
cout<<pr+1;
}
cout<<endl;
cin>>k>>n>>m;
}
}