北京信息科技大学第十一届程序设计竞赛（重现赛）G kotori和抽卡（二）

链接：https://ac.nowcoder.com/acm/contest/940/G
来源：牛客网

题目描述
kotori最近喜欢上了lovelive这个游戏，因为她发现自己居然也是里面的一个人物。

lovelive有个抽卡系统。共有R、SR、SSR、UR四个稀有度，每次单抽对应稀有度的概率分别是80%，15%，4%，1%。

然而，kotori抽了很多次卡还没出一张UR，反而出了一大堆R，气得她想删游戏了。她想知道n次单抽正好出m张R卡的概率是多少？

输入描述:
两个正整数n和m（1<=m<=n<=50）
输出描述:
n次单抽正好出m张R的概率。保留四位小数。

动态规划，在i次抽到j张R的概率为在i-1次抽到j张R的概率乘这次没中的概率+在i-1次抽到j-1张R的概率乘这次中的概率
状态转移方程：a[i][j]=a[i-1][j-1]*0.8+a[i-1][j]*0.2;

代码

#include<bits/stdc++.h>
using namespace std;
#define PB push_back
#define LL long long
#define FI first
#define SE second
#define POP pop_back()
#define PII pair<LL,LL>
#define PCC pair<char,char>
#define endl '\n'
#define ls x<<1
#define rs x<<1|1
#define m(x) a[x].l+a[x].r>>1
 
const int N=1e3+7;
const int INF=1e8,mod=109;
 
double a[N][N];
int n,m;
 
int main()
{
    a[0][0]=1;
    cin>>n>>m;
    //80%
    for(int i=1;i<=n;i++){
        a[i][0]=a[i-1][0]*0.2;
        for(int j=1;j<=i;j++){
            a[i][j]=a[i-1][j-1]*0.8+a[i-1][j]*0.2;
        }
    }
    printf("%.4f",a[n][m]);
    return 0;
}