计蒜客 T3223 卡牌 题解

· · 题解

题目链接

显然取魔法和物理中较多的那一个，下面默认选择魔法。

考虑 dp。dp_{i,j} 表示有 i 个魔法和 j 个物理的生命期望，然后枚举增量是魔法还是物理， 如果是魔法，则是从上一个状态的生命 +1 乘选择魔法的概率，否则是生命 -1 再乘上选择物理的概率，即

dp_{i,j}=max(0,(dp_{i-1,j}+1)\times\frac{i}{i+j}+(dp_{i,j-1}-1)\times\frac{j}{i+j})

递推到 dp_{n,m} 即可，边界为 dp_{i,0}=i，时间复杂度为 O(Tnm)。

如果 m>n 记得在 dp 前要 swap(n,m)。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
const int N=1e3+100;
int n,m,t;
double dp[N][N];
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        n>=m?printf("1 "):printf("2 ");
        if(m>n) swap(n,m);
        for(int i=1;i<=n;i++) dp[i][0]=i;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++) dp[i][j]=max(0.0,(dp[i-1][j]+1)*i*1.0/(i+j)+(dp[i][j-1]-1)*j*1.0/(i+j));
        }
        //dp[i][j]=max(max(0.0,(dp[i-1][j]+1)*i*1.0/(i+j)),(dp[i][j-1]-1)*j*1.0/(i+j));
        printf("%.3lf\n",dp[n][m]);
    }
    return 0;
}