NC20265 计数+记忆化搜索

https://ac.nowcoder.com/acm/problem/20265

补充数据范围：k<=15, c<=5
我们尝试着模拟给砖块着色的过程，已经处理完[1,l]区间时，l+1位置可以安放除了color[l]之外任何一种颜色的砖块。这是一个很显然的状态转移的过程，接下来思考如何表示一个状态。如果朴素的表示，记录每种颜色剩了多少，那么是5^15的状态数，过大。这里我们要发现，剩余砖块数量相等的两种颜色，其实是“等价”的。于是我们可以把状态表示为：剩余砖块数量为i的颜色有多少种，这样的状态复杂度是15^5的，可行。
具体来讲，设dp[a][b][c][d][e][last]表示：在a种颜色剩余一块砖头，b种剩余两块……e种剩余5块，且上次用过的那块砖所属颜色还有last块的情况下，共有多少种染色方案。本题状态转移适合写成记忆化搜索，具体看代码。

#include<bits/stdc++.h>
using namespace std;

const int maxk=16;
const int mod=1e9+7;
#define ll long long
ll dp[maxk][maxk][maxk][maxk][maxk][6];

ll dfs(int a,int b,int c,int d,int e,int last){
    if(dp[a][b][c][d][e][last]||a+b+c+d+e==0){
        return dp[a][b][c][d][e][last];
    }
    ll res=0;
    if(a) res=(res+(a-(last==1?1:0))*dfs(a-1,b,c,d,e,0)%mod)%mod;
    if(b) res=(res+(b-(last==2?1:0))*dfs(a+1,b-1,c,d,e,1)%mod)%mod;
    if(c) res=(res+(c-(last==3?1:0))*dfs(a,b+1,c-1,d,e,2)%mod)%mod;
    if(d) res=(res+(d-(last==4?1:0))*dfs(a,b,c+1,d-1,e,3)%mod)%mod;
    if(e) res=(res+e*dfs(a,b,c,d+1,e-1,4)%mod)%mod;
    return dp[a][b][c][d][e][last]=res;
}

int main(){
    int k,c,cnt[maxk]={0};
    cin>>k;
    for(int i=1;i<=k;i++){
        cin>>c;
        cnt[c]++;
    }
    dp[0][0][0][0][0][0]=1;
    cout<<dfs(cnt[1],cnt[2],cnt[3],cnt[4],cnt[5],0)%mod<<endl;
}