题解归档 - cf498B

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf498B
• 本地来源：problems/cf498B/idea.md
• 题目链接：https://codeforces.com/contest/498/problem/B
• 原始标题：498B Name That Tune

思路

498B Name That Tune

题意

按顺序播放 n 首歌，每首有识别率 p_i% 与副歌时刻 t_i。每秒末以 p_i% 独立识别；若到第 t_i 秒仍未识别则必定识别。总时长 T 秒，求期望识别歌曲数。

做法

逆序 DP：dp[i][rem] = 从第 i 首起、剩余 rem 秒时的期望识别数。

对歌曲 (p, t)，令 q = p/100，每秒未识别概率 (1-q)，第 k 秒识别权重 w_k = q(1-q)^{k-1}，强制识别权重 w_t = (1-q)^{t-1}。

dp[i][rem] = Σ_{k=1}^{min(t-1,rem)} w_k · (1 + dp[i+1][rem-k])
           + [rem≥t] · w_t · (1 + dp[i+1][rem-t])

rem=0 时为 0。答案 dp[0][T]。

优化

内层对 k 求和用滑动窗口 O(T) 每层，总 O(nT)：

• t=1：无提前识别项
• t=2：S[rem] = q · dp[i+1][rem-1]
• t≥3：窗口满后 S[rem] = q·nxt[rem-1] + (1-q)·S[rem-1] - (1-q)·w_{t-1}·nxt[rem-t]

验证

• 四组官方样例
• Python 对拍 500 组 (n,T≤25) 与 O(nT²) 暴力 DP 一致
• Kali 远端暂不可达，未跑 stress.py

结论

AC 预期；Div.1 B，期望 DP + 滑动窗口。

代码

来源：problems/cf498B/solution.cpp

/* Author: likely
 * Time: 2026-06-08 04:25:57
**/
#include<bits/stdc++.h>
#define ll long long
#define ld long double
using namespace std;
const ll maxn=5005;
ll n,T,i,j,k,p[maxn],ti[maxn];
ld q,onq,wti,wtm,S,pr,cur[maxn],nxt[maxn];
int main(){
    cin>>n>>T;
    for(i=1;i<=n;i++){
        cin>>p[i]>>ti[i];
    }
    for(k=0;k<=T;k++) nxt[k]=0.0;
    for(i=n;i>=1;i--){
        q=(ld)p[i]/100.0;
        onq=1.0-q;
        wti=1.0;
        for(j=1;j<ti[i];j++) wti*=onq;
        S=0.0;
        for(k=0;k<=T;k++){
            if(k==0){
                cur[k]=0.0;
                continue;
            }
            if(ti[i]==1) S=0.0;
            else if(ti[i]==2) S=q*nxt[k-1];
            else{
                S=q*nxt[k-1]+onq*S;
                if(k>ti[i]-1){
                    wtm=q;
                    for(j=1;j<ti[i]-1;j++) wtm*=onq;
                    S-=onq*wtm*nxt[k-ti[i]];
                }
            }
            if(k>=ti[i]) pr=1.0;
            else{
                pr=1.0;
                for(j=0;j<k;j++) pr*=onq;
                pr=1.0-pr;
            }
            cur[k]=pr+S;
            if(k>=ti[i]) cur[k]+=wti*nxt[k-ti[i]];
        }
        for(k=0;k<=T;k++) nxt[k]=cur[k];
    }
    cout<<fixed<<setprecision(9)<<nxt[T]<<endl;
    return 0;
}