1079: [SCOI2008]着色方案（dp之记忆化搜索）

本文主要是介绍1079: [SCOI2008]着色方案（dp之记忆化搜索），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接
题意：略
解答：考虑到每种颜色最多只能涂5个，设dp[a][b][c][d][e][last]：能涂一个格子的颜色有a种，能涂2个格子的颜色有b种，能涂3个格子的颜色有c种，能够涂4个格子的颜色有d种，能够涂5个格子的颜色有e种，且上一次涂的是last，的方案数。
能够想到的是，比如一种颜色x能涂3个格子，当我们使用它涂一个格子后，那么它就会变为能涂2个格子的类别中去了。这一点决定了转移的判断。


#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define pb push_back
#define X first
#define Y second
#define cl(a,b) memset(a,b,sizeof(a))
typedef pair<int,int> P;
const int maxn=1005;
const int inf=1<<27;
#define mod 1000000007LL dp[17][17][17][17][17][7];
bool vis[17][17][17][17][17][7];
int x[7];
LL dfs(int a,int b,int c,int d,int e,int last){if(vis[a][b][c][d][e][last])return dp[a][b][c][d][e][last];if(a+b+c+d+e==0)return 1;LL ans=0;if(a)ans+=(a-(last==2))*dfs(a-1,b  ,c,d,e,1)%mod;//解释，last==2，last表示上一次使用了，能涂2个格子的颜色，假设为x,那么上一次用x涂了一个格子后,x颜色就还能在涂一个格子了，也就是x算到能涂一个格子的颜色里了，所以，要去掉，也就是a-(last==2)if(b)ans+=(b-(last==3))*dfs(a+1,b-1,c,d,e,2)%mod;if(c)ans+=(c-(last==4))*dfs(a,b+1,c-1,d,e,3)%mod;if(d)ans+=(d-(last==5))*dfs(a,b,c+1,d-1,e,4)%mod;if(e)ans+=(e-(last==6))*dfs(a,b,c,d+1,e-1,5)%mod;vis[a][b][c][d][e][last]=true;return dp[a][b][c][d][e][last]=ans%mod;
}
int main(){int n;scanf("%d",&n);for(int i=0;i<n;i++){int t;scanf("%d",&t);x[t]++;}printf("%lld\n",dfs(x[1],x[2],x[3],x[4],x[5],0));return 0;
}