bzoj3191卡牌游戏

题目：https://www.lydsy.com/JudgeOnline/problem.php?id=3191

原本想模拟过程，从t个人推到1个人；

　　但是怎么转移呢？想状压，可是50位压不到角标里。

　　那就随便转移吧，把当前人的生存方案数加给所有有可能成为下一轮中自己的人。

#include<iostream>

#include<cstdio>

#include<cstring>

#define ll long long

using namespace std;

const int N=;

int n,m,a[N];

ll dp[N][N],sum;

int main()

{

    scanf("%d%d",&n,&m);

    for(int i=;i<=m;i++)scanf("%d",&a[i]);

    dp[n][]=;

    for(int t=n;t>;t--)

        for(int i=;i<=n;i++)

            if(dp[t][i])

            {

//                printf("t=%d i=%d dp=%d\n",t,i,dp[t][i]);

                for(int j=;j<=m;j++)

                {

                    int c=a[j]%t,l=i+c+,r=i-(t-c-);

//                    printf("i=%d aj=%d l=%d r=%d\n",i,a[j],l,r);

                    if(l>r)for(int k=;k<=n;k++)if(k>=r||k<=l)dp[t-][k]+=dp[t][i];

                    else for(int k=l;k<=r;k++)

                        dp[t-][k]+=dp[t][i];

                }

            }

    for(int i=;i<=n;i++)sum+=dp[][i];

    for(int i=;i<=n;i++)

        printf("%.2lf",(double)dp[][i]*/(double)sum),cout<<"% ";

    return ;

}

这当然是不对的。那个“有可能成为下一轮中自己的人”不能保证就是下一轮中的自己。

那怎么办？看看TJ，发现大家是用相对编号来记录下一轮中的自己是哪个人的。

　　用记忆化搜索可以想得更灵活一点。以后尝试用这个角度思考。不然自己容易想不出来……

概率不用每一步都算好。可以之前一直算的是方案数，最后再换算成概率。有时候这样比较方便。

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

const int N=;

int n,m,a[N];

bool vis[N][N];

double dp[N][N],sum;

double sol(int i,int j)

{

    if(vis[i][j])return dp[i][j];vis[i][j]=;

    if(i==)return dp[i][j]=;

    for(int k=;k<=m;k++)

        if(a[k]%i!=j%i)//j%i,不是j (j==i)

            dp[i][j]+=sol(i-,(j-(a[k]%i)+i)%i);

//    dp[i][j]/=m;

    return dp[i][j];

}

int main()

{

    scanf("%d%d",&n,&m);

    for(int i=;i<=m;i++)scanf("%d",&a[i]);

    for(int i=;i<=n;i++)sum+=sol(n,i);

    for(int i=;i<=n;i++)

    {

        printf("%.2lf%%",sol(n,i)/sum*);

        if(i!=n)printf(" ");

    }

    return ;

}