BZOJ 3450：Tyvj1952 Easy——期望 DP 計算 OX 序列得分

題目描述

長度 n 的序列，字符為 'o'、'x'、'?'。連續 k 個 'o' 得分 k²。'?' 等概率為 'o' 或 'x'。求期望總得分。

DP 狀態定義

• L[i]：第 i 位結尾連續 'o' 的期望長度
• F[i]：前 i 位的期望總得分

遞推公式

if s[i] == 'o':  L[i] = L[i-1] + 1,  F[i] = F[i-1] + 2*L[i] - 1
if s[i] == 'x':  L[i] = 0,           F[i] = F[i-1]
if s[i] == '?':  L[i] = (L[i-1] + 1) / 2,  F[i] = F[i-1] + L[i-1] + 0.5

推導說明

• 新增 'o' 使連續長度從 k-1 變 k，得分增量 k² - (k-1)² = 2k-1
• '?' 時：以 1/2 概率延長（增量 2(L+1)-1），1/2 概率歸零（增量 0），期望增量 (2L+1)/2 = L+0.5
• 期望長度遞推同理

C++ 實現

#include <cstdio>
using namespace std;
double L[300005], F[300005];
char s[300005];
int main() {
    int n; scanf("%d%s", &n, s+1);
    for (int i = 1; i <= n; ++i) {
        if (s[i] == 'o') {
            L[i] = L[i-1] + 1;
            F[i] = F[i-1] + 2*L[i] - 1;
        } else if (s[i] == 'x') {
            L[i] = 0;
            F[i] = F[i-1];
        } else { // '?'
            L[i] = (L[i-1] + 1) / 2.0;
            F[i] = F[i-1] + L[i-1] + 0.5;
        }
    }
    printf("%.4lf\n", F[n]);
    return 0;
}

複雜度

• 時間：O(n)
• 空間：O(n) 可優化至 O(1)