题解：P17721 「FunMusic OI 1D」爱我还是他 / Who Do You Love

· · 题解

注意到，当我们对 i 使用 3 次操作一时，其等价于对 i 和 i+1 分别使用 1 次操作二；当我们对 i 使用 3 次操作三时，其等价于对 i 使用 3 次操作二，对 i+1 使用 1 次操作二。

而每个位置的操作二是互相独立的，我们可以令 f_{i,j} 表示前 i-1 个位置全部清空，第 i 个还剩下 j 个王的状态是否可以达到。由第一段的推论，对于每个位置，会影响到 i+1 的操作一、三分别最多只有 2 次，故 j 的取值不超过 8。

最终只需要判断 f_{n,0} 是否为真。

对于一个值为真的 f_{i-1,k}，为了清空位置 i-1，我们可以枚举对 i-1 操作三的次数记为 l，则操作一的次数为 k-3l，位置 i 就减少了 l+(k-3l) 个王。转移到 f_{i,a_i-(l+k-3l)}。

对于一个值为真的 f_{i,j}，为了实现操作二，我们只需更新 f_{i,j\bmod 3}，f_{i,j\bmod 3+3} 和 f_{i,j\bmod 3+6} 的值即可，注意判断 j 与 3 和 6 的大小关系。

代码如下，可供参考：

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int T,n,a[N],f[N][10];
int main(){
    cin>>T;
    while(T--){
        cin>>n;
        for(int i=1;i<=n;i++)cin>>a[i];
        f[1][a[1]%3]=1;
        if(a[1]>=3)f[1][a[1]%3+3]=1;
        if(a[1]>=6)f[1][a[1]%3+6]=1;
        for(int i=2;i<=n;i++){
            for(int k=0;k<=8;k++){
                if(!f[i-1][k])continue;
                for(int l=0;l<=k/3;l++){
                    int j=a[i]-l-k+l*3;
                    if(j>=0){
                        if(j<=8)f[i][j]=1;
                        f[i][j%3]=1;
                        if(j>=3)f[i][j%3+3]=1;
                        if(j>=6)f[i][j%3+6]=1;
                    }
                }
            }
        }
        cout<<(f[n][0]?"YES\n":"NO\n");
        memset(f,0,sizeof f);
    }
    return 0;
}