AtCoder Beginner Contest 275 E F

E - Sugoroku 4

题意：从 0 走到 n ，有 k 次操作，每次会丢出一个骰子，骰子上的数字为\([1,m]\)，等概率出现

问到达 n 的概率

思路：

\(dp[i][k]\)表示用了 k 次操作到达位置 i 的概率

题意说到如果当前的位置 + 骰子数字 超出 n 的话，是会折返的

初始化 \(dp[0][0]=1\)然后对每一次操作进行dp即可

#include<bits/stdc++.h>
#define ll  long long
#define int long long 
#define endl '\n'
using namespace std;
const int N=1e3+5;
const int mod=998244353;
const int inf=0x3f3f3f3f;
int n,m,K;
ll dp[N][N];
ll qpow(ll a,ll b){
    ll res=1;
    while(b){
        if(b&1){
            res=res*a%mod;
        }
        b>>=1;
        a=a*a%mod;
    }
    return res;
}
// dp[i][j]
// j operations and now at the i
void solve(){
    cin>>n>>m>>K;
    if(m*K<n){
        cout<<0<<'\n';
        return;
    }
    dp[0][0]=1;
    ll ans=0;
    for(int k=1;k<=K;k++){
        for(int j=1;j<=m;j++){
            for(int i=0;i<n;i++){
                if(i+j<=n){
                    dp[i+j][k]+=dp[i][k-1]*qpow(m,mod-2)%mod;
                    dp[i+j][k]%=mod;
                }
                else {
                    dp[2*n-(i+j)][k]+=dp[i][k-1]*qpow(m,mod-2)%mod;
                    dp[2*n-(i+j)][k]%=mod;
                }
            }
        }
        ans+=dp[n][k];
        ans=ans%mod;
    }
    cout<<ans<<'\n';
}
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int T = 1;
    // cin >> T;
    while(T--){solve();}
    
}

F - Erase Subarrays

题意：给出一个数组，问是否能通过删掉一些连续的子数组（操作一次即删掉一个连续子数组），剩下的数组之和为 x

若可以，求出最小操作次数，反之答案为-1

思路：

\(dp[i][j][k]\)表示操作前 i 个数字得到和为 j 的最小操作数，其中第三维是 0/1,1表示第i个不删

转移

\(dp[i][j][0]=dp[i-1][j][0]\)

\(dp[i][j][0]=dp[i-1][j][1]+1\)

\(dp[i][j][1]=dp[i-1][j-a[i]][0/1]\)

#include<bits/stdc++.h>
#define ll  long long
#define int long long 
#define endl '\n'
using namespace std;
const int N=3100;
const int mod=998244353;
const int inf=0x3f3f3f3f;
int n,m,k;
int a[N];
int dp[N][N][2];
void solve(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    // memset(dp,0x3f,sizeof(dp));
    for(int i=0;i<=n;i++){
        for(int j=0;j<=m;j++){
            dp[i][j][1]=dp[i][j][0]=inf;
        }
    }
    dp[0][0][1]=0;
    for(int i=1;i<=n;i++){
        for(int j=0;j<=m;j++){
            dp[i][j][0]=min(dp[i][j][0],dp[i-1][j][0]);
            dp[i][j][0]=min(dp[i][j][0],dp[i-1][j][1]+1);
            if(j-a[i]>=0){
                dp[i][j][1]=min(dp[i][j][1],dp[i-1][j-a[i]][0]);
                dp[i][j][1]=min(dp[i][j][1],dp[i-1][j-a[i]][1]);
            }
        }
    }

    for(int i=1;i<=m;i++){
        // if(dp[n][i])
        int minn=min(dp[n][i][1],dp[n][i][0]);
        if(minn==inf){
            cout<<-1<<'\n';
        }
        else cout<<minn<<'\n';
    }
}
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int T = 1;
    // cin >> T;
    while(T--){solve();}
    
}