Help needed in optimising the memoized solution!!!

Правка en3, от Vesper_Lynd, 2018-08-18 16:54:04

why memoized solution fails in this problem: Source //below is the given code

//can you help me spot some patterns to optimise it!!!

lli solve(lli x,lli y,lli e,lli w) {

if(dp[x][y]!=100000)

{

return dp[x][y];

} if((x*x+y*y)==e*e) { return 0;
} for(int i=1;i<=N;i++) { if(((x+coins[i].a)*(x+coins[i].a)+(y+coins[i].b)*(y+coins[i].b))<=e*e) { dp[x][y]=min(dp[x][y],(solve(x+coins[i].a,y+coins[i].b,e,i)+1)); } } return dp[x][y]; }

int main() {

cin>>n;

for(int i=1;i<=n;i++) {

f=0;

for(int j=0;j<1001;j++) { for(int k=0;k<1001;k++) dp[j][k]=100000; }

for(int i=0;i<100000;i++) dp1[i]=100000; cin>>N>>e;

for(int j=1;j<=N;j++) { cin>>x>>y; coins[j].a=x; coins[j].b=y; } lli d=solve(0,0,e,0); if(d==100000) cout<<"not possible"<<endl; else cout<<d<<endl; } }

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en5 Английский Vesper_Lynd 2018-08-18 18:10:37 860
en4 Английский Vesper_Lynd 2018-08-18 16:54:47 28
en3 Английский Vesper_Lynd 2018-08-18 16:54:04 14
en2 Английский Vesper_Lynd 2018-08-18 16:53:04 14
en1 Английский Vesper_Lynd 2018-08-18 16:51:48 1181 Initial revision (published)