description

  偶然间,chnlich 发现了他小时候玩过的一个游戏“魂斗罗”,于是决定怀旧。但是这是一个奇怪的魂斗罗 MOD。

  有 N 个关卡,初始有 Q 条命。

  每通过一个关卡,会得到 u 分和1条命,生命上限为 Q。其中 u=min(最近一次连续通过的关数,R)。

  若没有通过这个关卡,将会失去1条命,并进入下一个关卡。

  当没有生命或没有未挑战过的关卡时,游戏结束,得到的分数为每关得到的分数的总和。

  由于 chnlich 好久不玩这个游戏了,每条命通过每个关卡的概率均为p(0<=p<=1),原先 chnlich 的最高分纪录是 S。



  现在 chnlich 想要知道,当 p 至少为多少时,chnlich 期望获得的总分数能够超过原先的最高分。

analysis

• 很好的二分\(+\)矩乘\(+DP\)题

• 由题解可得\(50pts\)的\(DP\)方程

\[g[i+1][min(j+1,R)][min(k+1),Q]+=g[i][j][k]*p\]

\[g[i+1][0][k-1]+=g[i][j][k]*(1-p)\]

\[Answer+=g[i][j][k]*p*(j+1)\]

• 二分一个最小可能的\(p\)，用矩乘判断是否可行

• 对于每一种积分\(x\)命\(y\)条的状态，用不同的数字表示来压状态

• 可以知道当积分\(≥q\)时（连赢至少\(q\)次），命一定为\(q\)条，这样可以省去很多状态

• 压完状态之后，就只有\(30\)种左右的状态，可以矩乘快速幂

• 具体就是把按照方程每种状态转移到其他状态的矩阵位置加上贡献\(p,1-p\)或\(p*(j+1)\)

• 注意那个\(Answer\)由所有的情况累加到最终状态，即为积分\(0\)命\(0\)条的情况

• 判断最终矩阵第起始状态行（积分\(0\)命\(q\)条）第终止状态列（积分\(0\)命\(0\)条）的值是否大于\(s\)即可

• 下次遇到矩乘题目，要认真想想\(DP\)，不要被矩阵怎么推给卡住

code

#pragma GCC optimize("O3")
#pragma G++ optimize("O3")
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define MAXN 40
#define ll long long
#define reg register ll
#define fo(i,a,b) for (reg i=a;i<=b;++i)
#define fd(i,a,b) for (reg i=a;i>=b;--i)

using namespace std;

ll statu[10][50];
ll n,m,r,q,s;

struct matrix
{
    double f[MAXN][MAXN];
    matrix(){memset(f,0,sizeof(f));}
};
inline ll read()
{
    ll x=0,f=1;char ch=getchar();
    while (ch<'0' || '9'<ch){if (ch=='-')f=-1;ch=getchar();}
    while ('0'<=ch && ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*f;
}
inline ll max(ll x,ll y){return x>y?x:y;}
inline ll min(ll x,ll y){return x<y?x:y;}
inline matrix operator*(matrix a,matrix b)
{
    matrix c;
    fo(i,1,n)fo(j,1,n)fo(k,1,n)c.f[i][j]+=a.f[i][k]*b.f[k][j];
    return c;
}
inline matrix pow(matrix x,ll y)
{
    matrix z;
    fo(i,1,n)z.f[i][i]=1;
    if (y==0)return z;
    while (y)
    {
        if (y&1)z=z*x;
        x=x*x,y>>=1;
    }
    return z;
}
inline bool judge(double p)
{
    matrix a;n=0;
    fo(i,0,q)//statu[i][j]表示剩i条命有j积分的情况
    {
        ll tmp=i==q?r:min(i-1,r);
        fo(j,0,max(tmp,0))statu[i][j]=++n;
    }
    a.f[1][1]=1;
    fo(i,1,q)
    {
        ll tmp=i==q?r:min(i-1,r);
        fo(j,0,max(tmp,0))
        {
            ll x=statu[i][j],y=statu[i-1][0],z=statu[min(i+1,q)][min(j+1,r)];
            if (i>1)a.f[x][y]=1-p;a.f[x][z]=p,a.f[x][statu[0][0]]=p*min(j+1,r);
        }
    }
    matrix b=pow(a,m);
    return b.f[statu[q][0]][statu[0][0]]>s;
}
int main()
{
    freopen("T2.in","r",stdin);
    m=read(),r=read(),q=read(),s=read();
    if (!judge(1)){printf("Impossible.\n");return 0;}
    ll l=0,r=10000000,tmp=r,mid=(l+r)>>1;
    while (l<=r)
    {
        mid=(l+r)>>1;
        if (judge(1.0*mid/tmp))r=mid-1;else l=mid+1;
    }
    printf("%.6lf\n",1.0*l/tmp);
    return 0;
}

【JZOJ2867】Contra

原文：https://www.cnblogs.com/horizonwd/p/11293748.html