【状态设计优化DP】ABC307 E

﹏ヽ暗。殇╰゛Y 2024-03-17 18:11 31阅读 0赞

[E - Distinct Adjacent (atcoder.jp)][E - Distinct Adjacent _atcoder.jp]

题意：

![d9735a1ecda945c9b061ccd01fa1be64.png][]

思路：

组合问题，考虑DP或组合数

组合数不好考虑，我们去考虑DP

因为是个环，我们把环拆成一条链，然后加一个N+1，颜色和起点1相同，在这条链上DP

先考虑暴力DP

设dp\[i\]\[x\]表示第i个元素，选的颜色为x的方案数

这样转移方程非常好转移：

dp\[i\]\[x\]+=dp\[i-1\]\[y\]，(if x!=y && i!=N)

dp\[i\]\[x\]+=dp\[i-1\]\[y\]，(if x!=y && i==N && x!=a)

但是这样设计既会爆时间也会爆空间，因此我们考虑重新设计状态

注意到，我们在转移的过程中

当i != N时，我们关注的只是和前面那个颜色是否相同

当i == N时，我们关注的是和前面那个颜色是否相同 + 和第一个元素是否相同

因此存在着很多无效状态，**我们只需要记录和第一个元素是否相同即可**

题解原话是这么说的：

> But on second thought, we observe that we do not need to distinguish all integers assigned to the last person, but only whether the last integer equals the one given to the first person.

那么我们可以这样设计状态

设dp\[i\]\[0\]表示第 i 个元素，和第一个元素颜色不同的方案数

dp\[i\]\[1\]表示第 i 个元素，和第一个元素颜色相同的方案数

那么就可以转移了

**感觉这种状态优化的DP应该先考虑暴力DP怎么写，然后再去看在转移过程中实际需要记录的维数是什么就可以**

#include <bits/stdc++.h>
    
    #define int long long
    
    using namespace std;
    
    const int mxn=1e6+10;
    const int mxe=2e5+10;
    const int mod=998244353;
    
    int N,M;
    int dp[mxn][2];
    
    void solve(){
        cin>>N>>M;
        dp[1][1]=M;
        for(int i=2;i<=N;i++){
            dp[i][1]=dp[i-1][0];
            dp[i][0]=(dp[i-1][0]*(M-2)%mod+dp[i-1][1]*(M-1)%mod)%mod;
        }
        cout<<dp[N][0]<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        while(__--)solve();return 0;
    }

[E - Distinct Adjacent _atcoder.jp]: https://atcoder.jp/contests/abc307/tasks/abc307_e
[d9735a1ecda945c9b061ccd01fa1be64.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/bb86b9397a5a40f4aeb453541fb723d1.png