Блог пользователя ayushexel

Автор ayushexel, история, 8 лет назад, По-английски

Problem link => http://www.spoj.com/problems/BACKPACK/

My solution :

#include <iostream>
#include <map>
#include <tuple>
using namespace std;
multimap<int,pair<int,int>>data; //to store attachments

int wt[61],val[61];//to store main goods

int solve(int n,int vol){
if(n<1||vol<0||wt[n]>vol)
  return 0;
if(wt[n]==-1)
  return solve(n-1,vol);
int w = wt[n], v = val[n];
int ret = solve(n-1,vol-w)+w*v;
auto range = data.equal_range(n); //check if there are any attachments
int coun = v*w,cw = w;
for(auto i=range.first;i!=range.second;i++){

int w1 = i->second.first,v1= i->second.second;
  coun+=w1*v1;
  cw += w1;
 ret = max(ret,solve(n-1,vol-w-w1)+w*v+w1*v1); //take only this attachment

ret = max(ret,solve(n-1,vol-cw)+coun); //take this attachment along with previous one *there can be only 2 attachments at max*


}
return ret;
}

int main ()
{
int t;
cin>>t;
while(t--){
  int vmax,n;
  cin>>vmax>>n;
  int a,b,c;
  int sz = 1;
  for(int i=1;i<=n;i++){
    cin>>a>>b>>c;
    if(c==0){ //treat this as a main good
      wt[i] = a;
      val[i]=b;

    }else{ //treat this as an attachment
      data.insert(make_pair(c,make_pair(a,b)));
      wt[i] = -1; //this indicates that this index is an attachment
    }
  }
 
  cout << solve(n,vmax) << endl;
}

}

So this is just a backtrack solution and I've not memoized it yet. But the problem is I'm getting "Wrong Answer" error on submitting this code. I have checked this code on various test cases and its working fine . So, waht's the error and how can I fix it ?

Полный текст и комментарии »

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

Автор ayushexel, история, 8 лет назад, По-английски

problem link : http://www.spoj.com/problems/MBALL/

my solution :

#include <iostream>
#include <memory.h>
using namespace std;

long long dp[100002][6];

long long solve(long long b,long long c){
if(b==0)
return 1;
if(b<0||c==5)
return 0;
if(dp[b][c]!=-1){
return dp[b][c];
}
long long ret = 0;
if(c<=0){
for(long long i=2;i<=b;i+=2)
ret += solve(b-i,1);
}

if(c<=1){
for(long long i=3;i<=b;i+=3)
ret += solve(b-i,2);
}

if(c<=2){
for(long long i=6;i<=b;i+=6){
ret += solve(b-i,3);
}
}

if(c<=3){
for(long long i=7;i<=b;i+=7){
ret += solve(b-i,4);
}
}

if(c<=4){
for(long long i=8;i<=b;i+=8){
ret += solve(b-i,5);
}
}

return dp[b][c] = ret;
}

int main()
{
int n;
cin>>n;
memset(dp,-1,sizeof(dp));
while(n--){

int s;
cin>>s;
cout << solve(s,0) << endl;
}
return 0;
}

The code is working fine but on submitting i'm getting "time limit exceeded" error . I don't want to use iterative approach . So, how can the time limit be reduced without using iterative DP ?

Полный текст и комментарии »

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится