P11126 题解

· · 题解

场切题，但是似乎还有一个 \frac{1}{1400} 倍常数的 O(n^3) 做法？

Descr

题目写的够清楚了。

Sol

考虑 DP。

首先把所有的 a_i 放进桶里，记 i 出现的次数为 c_i。

从小到大分为两种模式匹配，对于数 i，匹配 \{i,i,i\} 或 \{i-2,i-1,i\}，并且一个数匹配过了就再也不管这个数了。

由此可以设计 naive 的状态 f_{i,j,k} 表示当前匹配完了 i，i 这个数还剩下 j 个，i-1 这个数还剩下 k 个，i-2 及以前的数没有剩余。

从 f_{i,j,k} 转移到 f_{i+1,j',k'} 时因为要保证前面没有剩下的数，所以要把 k 个 i-1 全部匹配完，再枚举第 i+1 个数有 t 次自己跟自己匹配，可以得到如下方程：

f_{i,j,k}\rightarrow f_{i+1,c_{i+1}-3t-k,j-k}

观察到枚举 t 的过程实际上是对 f_{i+1,c{i+1}-k,j-k} 做一个前缀隔 3 的加，所以可以优化转移为以下两个方程：

\begin{aligned} f_{i,j,k}&\rightarrow f_{i+1,c_{i+1}-k,j-k}\\ f_{i,j,k}&\rightarrow f_{i,j-3,k} \end{aligned}

滚掉 DP 数组第一维后，直接做这个 DP 并跑一些大的数据发现很快，考虑分析复杂度。

注意到对于 f_{i,j,k}，j 的上界是 c_{i}，k 的上界是 c_{i-1}，所以总状态数是 \sum c_ic_{i-1} 的。

我们在小学二年级学过 a^2+b^2\geq 2ab 和 (a+b)^2\geq a^2+b^2，于是有：

\begin{aligned} m^2&=(\sum c_i)^2\\ &\geq \sum c_i^2\\ &\geq \sum c_ic_{i-1} \end{aligned}

于是状态数是 O(m^2) 的，又因为转移是均摊 O(1) 的所以总复杂度是 O(m^2) 的。

Code

#include <bits/stdc++.h>
using namespace std;
//#define int long long
typedef pair<int,int> pii;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
const int N=5e3+10,INF=0x3f3f3f3f,mod=1e9+7;
int n,m,c[N];
int f[N][N],g[N][N];
void solve1(){
    g[0][0]=1;
    for(int i=0;i<m;i++){
        for(int j=0;j<=(i>0?c[i]:0);j++){
            for(int k=0;k<=min((i>1?c[i-1]:0),j);k++){
                if(!g[j][k])continue;
                f[c[i+1]-k][j-k]=(f[c[i+1]-k][j-k]+g[j][k])%mod;
            }
        }
        for(int j=c[i+1];j>=0;j--)
            for(int k=0;k<=c[i+1];k++)
                f[j][k]=(f[j][k]+f[j+3][k])%mod;
        for(int j=0;j<=c[i];j++)
            for(int k=0;k<=c[i];k++)
                g[j][k]=0;
        for(int j=0;j<=c[i+1];j++)
            for(int k=0;k<=c[i+1];k++)
                g[j][k]=f[j][k],f[j][k]=0;
    }
    cout<<g[0][0]<<endl;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        int t;cin>>t;
        c[t]++;
    }
    solve1();
    return 0;
}