[ROIR 2025] 寻找宝藏 题解

· · 题解

dp，通过简单观察，发现考虑第 i 列统计方案数时，只需知道如图画的那几条线就行了。

并且这样转移是方便的，对于第 i 列，我们只需记录红颜色方框内的状态并且在转移至 i+1 时状压枚举 i+1 那一列就行了，因此我们可以直接设出一个 k 维 dp，由于定义太长，不做阐述，这个时候你可能想法是直接分 k=1,2,\cdots,7 这几种情况写代码，但是麻烦了，你可以就设一个 7 维 dp 数组，转移时保持后 \min(6-k,0) 维是 0 就行了，具体实现见代码。

时间复杂度 O(nk 2^kk!)。（目前为最优解 rk1）

#include<bits/stdc++.h>
using namespace std;
#define mod 1000000007
int n,k,a[202],dp[202][7][6][5][4][3][2],ans;
signed main()
{
    cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>a[i];
    dp[0][0][0][0][0][0][0]=1;
    for(int i=1;i<=n;i++)
        for(int j1=0;j1<=min(6,a[i])*(k>=7);j1++)
            for(int j2=0;j2<=min(5,a[i]-j1)*(k>=6);j2++)
                for(int j3=0;j3<=min(4,a[i]-j1-j2)*(k>=5);j3++)
                    for(int j4=0;j4<=min(3,a[i]-j1-j2-j3)*(k>=4);j4++)
                        for(int j5=0;j5<=min(2,a[i]-j1-j2-j3-j4)*(k>=3);j5++)
                            for(int j6=0;j6<=min(1,a[i]-j1-j2-j3-j4-j5)*(k>=2);j6++)
                            {
                                for(int s=0;s<(1<<k);s++)
                                {
                                    int f=__builtin_popcount(s);
                                    if(f+j1+j2+j3+j4+j5+j6!=a[i]) continue;
                                    int p1=j2+((s&(1<<5))!=0);p1*=(k>=7);
                                    int p2=j3+((s&(1<<4))!=0);p2*=(k>=6);
                                    int p3=j4+((s&(1<<3))!=0);p3*=(k>=5);
                                    int p4=j5+((s&(1<<2))!=0);p4*=(k>=4);
                                    int p5=j6+((s&(1<<1))!=0);p5*=(k>=3);
                                    int p6=((s&(1<<0))!=0);p6*=(k>=2);
                                    dp[i][p1][p2][p3][p4][p5][p6]=(dp[i][p1][p2][p3][p4][p5][p6]+dp[i-1][j1][j2][j3][j4][j5][j6])%mod;
                                    if(i==n) ans=(ans+dp[i-1][j1][j2][j3][j4][j5][j6])%mod;
                                }
                            }
    cout<<ans;
    return 0;
}