[清橙A1295]necklace【dp】

【题目描述】

试题来源

　　清华大学2011年百名信息学优秀高中学子夏令营

问题描述

　　有人打算送给你一条宝石项链，包含了N颗五颜六色（一共有M种颜色）的宝石。因为本问题中你只关心每个宝石的颜色，而且项链现在两头还没有接在一起，它可以被看成是一个数字串。
　　你希望在五颜六色的宝石中看到连续的一段同色宝石。因此，你定义一根宝石项链的幸运度是它最长的由同色宝石构成的连续子串的长度。比如，项链112322211的幸运度是3，因为它包括了由同色宝石构成的子串222。而首尾的两个11并不构成连续1111，因为这个项链现在是串形的而不是环形的。
　　然而，你还没有见到这个项链。你只知道每个宝石是每种颜色的概率。并且，已知每个宝石的颜色分布是独立的。现在你希望在真的见到这条项链之前计算一下，这条项链的幸运度的期望是多少？

输入格式

　　输入的第一行有两个正整数N和M。
　　后面N行每行有M个非负实数。其中第i行第j列的数P_(i,j)含义是第i个宝石是颜色j的概率是P_(i,j)。每行的M个实数保证和为1。

输出格式

　　一个实数，即这条项链的幸运度的期望。四舍五入至小数点后6位。

样例输入

样例输出

2.250000

样例说明

　　我们用1和2来分别表示两种颜色的宝石，则这串项链有四种等概率的情形：1121，1122，1221和1222。它们的幸运度分别是2，2，2，3，因此期望的幸运度是2.25。

数据规模和约定

　　30%的数据满足N≤16,M≤3。
　　60%的数据满足N≤100。
　　100%的数据满足2≤N≤1000,2≤M≤10。

【题解】

不难想到一个O(n^3*m^2)的朴素dp，f[i][j][k][t]表示到第i个，最长连续段不大于j，末尾连续长度为k，末尾颜色为t，O(m)枚举下一位颜色转移。

考虑优化，其实我们不必要知道最后的连续段的长度，只要保证它不超过最长答案就行了。

如果添加了一个珠子使答案超过了限制，它的概率为，这一段全都为一种颜色的概率。

记p[i][j][k]表示珠子i..j颜色都为k的概率，f[i][j][k]表示到第i个，最长连续段不大于j,末尾颜色为k的概率，s[i][j]表示到第i个，最长连续段不大于的概率。

有f[i][j][k]=s[i-1][j]*p[i][i][k]-s[i-j][j]*p[i-j+1][i][k];

s[i][j]=sigma(f[i][j][k]) k=1..m;

时间复杂度O(n^2*m

/* --------------
    user Vanisher
    problem A1295
----------------*/
# include <bits/stdc++.h>
# define    ll      long long
# define    N       1010
# define    M       11
using namespace std;
int read(){
    int tmp=0, fh=1; char ch=getchar();
    while (ch<'0'||ch>'9'){if (ch=='-') fh=-1; ch=getchar();}
    while (ch>='0'&&ch<='9'){tmp=tmp*10+ch-'0'; ch=getchar();}
    return tmp*fh;
}
int n,m;
double p[N][N][M],f[N][N][M],s[N][N],ans;
int main(){
    n=read(), m=read();
    for (int i=1; i<=n; i++)
        for (int j=1; j<=m; j++)
            scanf("%lf",&p[i][i][j]);
    for (int i=1; i<=m; i++)
        for (int j=1; j<=n; j++)
            for (int k=j+1; k<=n; k++) 
                p[j][k][i]=p[j][k-1][i]*p[k][k][i];
    for (int i=0; i<=n; i++) s[0][i]=1;  
    for (int i=1; i<=n; i++)  
    {  
        for (int j=1; j<=n; j++)  
        for (int k=1; k<=m; k++)  
        {  
            f[i][j][k]=s[i-1][j]*p[i][i][k];  
            if (i-j-1>=0) f[i][j][k]-=(s[i-j-1][j]-f[i-j-1][j][k])*p[i-j][i][k];  
            s[i][j]+=f[i][j][k];  
        }  
    }  
    for (int i=1; i<=n; i++)  
        ans+=(s[n][i]-s[n][i-1])*i;  
    printf("%.6f",ans);  
    return 0;
}

)