Problem #3446 - ECNU Online Judge

6 年前

月考压轴题？是一道有点意思的dp，我用的是数组循环存数据，有几个地方有点小坑。附C++代码：

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n, k, x, y;
    cin>>n>>k;
    long double dp[7][12001];
    long double p=1.0/6.0;
    if(k>n*6 || k<n) {cout<<0; return 0;}
    for(int i=1; i<7; i++) dp[1][i]=p;
    for(int i=2; i<=n; i++)
    {
        x=i%7;
        y=(i-1)%7;
        for(int j=i; j<=6*i; j++)
        {
      dp[x][j]=0;
            if(j>6 && j>=i+5) {dp[x][j]+=dp[y][j-6]*p;}
            if(j>5 && j>=i+4) {dp[x][j]+=dp[y][j-5]*p;}
            if(j>4 && j>=i+3) {dp[x][j]+=dp[y][j-4]*p;}
            if(j>3 && j>=i+2) {dp[x][j]+=dp[y][j-3]*p;}
            if(j>2 && j>=i+1) {dp[x][j]+=dp[y][j-2]*p;}
            dp[x][j]+=dp[y][j-1]*p;
        }
    }
    printf("%.6llf\n",dp[n%7][k]);
    return 0;
}

回复 1 0

╮ 潜心 ╰

4 年，9 月前

这个题其实是赤裸裸的DP，本来还想蒙特卡洛模拟，后来时限劝退233
注意到k在[n, 6n]内才是合法的，不合法输出0
dp(i,j)表示扔出i个骰子得到j分的概率。
先初始化 dp[i, j] = 1/6 for j in range(1, 7)
然后开始逐层利用已求解的概率推下去
大概想法是比如说（2,6）可以从（1,1）到(1,5)共5个状态推上来（3,11）可以从（3,5）到（3,10）六个状态推上来
状态转移方程就是dp[i, j] = dp[i-1, j-num] / 6 for each num has (j-num >= 1 and num <= 6)
复杂度O(nk)，扫一遍就可以

回复 0 0