Prevent MLE in DP (Top down)

Revision en3, by myaw, 2015-08-16 20:26:58

I just solved this dp problem , i compared my code to an accepted code by trying random test cases , and it gives correct results , how ever it gives MLE in the onligne judge ( only 32M of memory )

So my question is how to prevent this ??

here is my code :

include <bits/stdc++.h>

define pb push_back

define rep(i,n) for(int i = 0; i < n; i++)

define ll long long

using namespace std; ll n,x,tot,ans1,ans2=11111111; ll memo[100005][101]; vector v; int solve(ll sum,int step,int chosen) { if(chosen==n/2) if(ans2-ans1>abs(abs(tot-2*sum))) { ans2=max(tot-sum,sum);ans1=min(tot-sum,sum); } if(sum>tot||step>=n) return 0;

if(memo[sum][step]!=-1) return memo[sum][step];

solve(sum+v[step],step+1,chosen+1); solve(sum,step+1,chosen); return memo[sum][step] = sum ; }

int main() { int tc; cin >> tc ; rep(qq,tc) { cin >> n ; v.clear(); tot=0; rep(i,n) { cin >> x ; v.pb(x); tot+=x; }

memset(memo, -1, sizeof(memo));
      solve(0,0,0);
      cout << "Case " << qq+1 << ": " << ans1 << " " <<ans2 <<endl;
 }
 return 0;

}

Tags dp, lightoj, mle

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English myaw 2015-08-16 21:17:52 1460
en3 English myaw 2015-08-16 20:26:58 137
en2 English myaw 2015-08-16 20:26:03 137
en1 English myaw 2015-08-16 20:25:19 1333 Initial revision (published)