what is the complexity for this dp solution !!??

Revision en1, by _QWOiNYUIVMPFSBKLiGSMAP_, 2018-02-19 09:55:56

the problem is http://codeforces.com/contest/513/problem/C the solution is http://codeforces.com/contest/513/submission/9761274

code

int n,l[6],r[6]; double dp[6][10009][6][6]; double bt(int i,int maxi,int eq,int gr) { if(i==n) { if(eq+gr>1&&gr<=1) return maxi; else return 0; } if(dp[i][maxi][eq][gr]!=-1) return dp[i][maxi][eq][gr]; double ret; if(maxi>=l[i]&&maxi<=r[i]) { if(gr) ret=((maxi-l[i])*bt(i+1,maxi,eq,gr)+bt(i+1,maxi,eq+1,gr))/(r[i]-l[i]+1); else ret=((maxi-l[i])*bt(i+1,maxi,eq,0)+bt(i+1,maxi,eq+1,0)+(r[i]-maxi)*bt(i+1,maxi,eq,1))/(r[i]-l[i]+1); } else if(maxi>r[i]) return bt(i+1,maxi,eq,gr); else if(maxi<l[i]) return bt(i+1,maxi,eq,gr+1); return dp[i][maxi][eq][gr]=ret; }

int main() { cin>>n; for(int f=0;f<n;f++) { cin>>l[f]>>r[f]; } for(int f1=0;f1<6;f1++) for(int f2=0;f2<10009;f2++) for(int f3=0;f3<6;f3++) for(int f4=0;f4<6;f4++) dp[f1][f2][f3][f4]=-1;

double ans=0;
for(int f=0;f<10009;f++)
{
ans+=bt(0,f,0,0);
}
cout<<setprecision(9)<<fixed<<ans<<endl;

}

History

Revisions

Rev. Lang. By When Δ Comment
en2 _QWOiNYUIVMPFSBKLiGSMAP_ 2018-02-19 09:57:56 1108
en1 _QWOiNYUIVMPFSBKLiGSMAP_ 2018-02-19 09:55:56 1310 Initial revision (published)