Educational DP Contest

ATcoder_link
夯实基础的好东西

I

记录一下此时第 i 个有多少概率小于等于 j 的就可以了。

#include<bits/stdc++.h>
using namespace std;
const int N=3005;
#define db double 
db dp[N][N];
int n;
db p[N];
int main(){
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)cin>>p[i];
    int ma=n/2;
    for(int i=0;i<=ma;i++) dp[0][i]=1;
    for(int i=1;i<=n;i++){
        db f=1-p[i],z=p[i];
        dp[i][0]=dp[i-1][0]*z;
        for(int j=1;j<=ma;j++) dp[i][j]=dp[i-1][j]*z+dp[i-1][j-1]*f;
    }
    printf("%.10lf",dp[n][ma]);
    return 0;
}

J

期望的经典题型。
首先几个盘子是等价的设 \(1,2,3\) 分别有 \(i,j,k\) 个。
则有 \(dp_{i,j,k}=1+dp_{i,j,k}*\frac{n-i-j-k}{n}+dp_{i-1,j,k}*\frac{i}{n}+dp_{i+1,j-1,k}*\frac{j}{n}+dp_{i,j+1,k-1}*\frac{k}{n}\)
简单化一下式子 \(n*dp_{i,j,k}=n+dp_{i,j,k}*(n-i-j-k)+dp_{i-1,j,k}*i+dp_{i+1,j-1,k}*j+dp_{i,j+1,k-1}*k\)
这傻逼练 latex 呢是吧 \((i+j+k)*dp_{i,j,k}=n+dp_{i-1,j,k}*i+dp_{i+1,j-1,k}*j+dp_{i,j+1,k-1}*k\)
\(dp_{i,j,k}=\frac{n+dp_{i-1,j,k}*i+dp_{i+1,j-1,k}*j+dp_{i,j+1,k-1}*k}{i+j+k}\)

然后注意下转移顺序就可以了喵。感觉有助于理解期望。
可能比较抽象：期望是转移走的概率，就是每个可能性的期望*概率，所以要从简单向复杂的推，从复杂的往简单的推应该能做但是式子未免太抽象了。反过来是好的！

//#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
const int N=305;
#define db double
db dp[N][N][N];
int n;
int cnt[5];
int main(){
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        int tmp;
        cin>>tmp;
        cnt[tmp]++;
    }
    for(int k=0;k<=n;k++){
        for(int j=0;j<=n;j++)
        for(int i=0;i<=n;i++){
            if(i||j||k){
                if(i)dp[i][j][k]+=dp[i-1][j][k]*i;
                if(j)dp[i][j][k]+=dp[i+1][j-1][k]*j;
                if(k)dp[i][j][k]+=dp[i][j+1][k-1]*k;
                (dp[i][j][k]+=n)/=(i+j+k);
            }
        }
    }
    cout<<dp[cnt[1]][cnt[2]][cnt[3]];
    return 0;
}

K

经典博弈题，如果一个点能到达必胜状态它就是必胜的。

//#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
int f[100005];
int a[105];
int n,k;
int main(){
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n>>k;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=k;i++){
        for(int j=1;j<=n;j++)
        f[i]|=((i-a[j]>=0)&&(!f[i-a[j]]));
    }
    puts(f[k]?"First":"Second");
    return 0;
}