what is the complexity for this dp solution !!??
Разница между en1 и en2, 1,108 символ(ов) изменены
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;↵
}
i wonder how this solution not TLE it is 1009*1009*6*6*6  which is TLE

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский _QWOiNYUIVMPFSBKLiGSMAP_ 2018-02-19 09:57:56 1108
en1 Английский _QWOiNYUIVMPFSBKLiGSMAP_ 2018-02-19 09:55:56 1310 Initial revision (published)