上海百度网站建设,网站前端浏览器兼容如何做,糕点网站策划书,网站备案的程序题目链接
思想
显然我们后面的决策是跟前一步相关的#xff0c;因此我们可以考虑DP#xff0c;可以用一个15维的数组来进行转移#xff0c;但是这样显然回mle#xff0c;所以我们考虑如何压缩状态#xff0c;由于1Ci51 C_i 51Ci5#xff0…题目链接
思想
显然我们后面的决策是跟前一步相关的因此我们可以考虑DP可以用一个15维的数组来进行转移但是这样显然回mle所以我们考虑如何压缩状态由于1Ci51 C_i 51Ci5所以我们可以有dp数组: dp[a1][a2][a3][a4][a5][last]dp[a_1][a_2][a_3][a_4][a_5][last]dp[a1][a2][a3][a4][a5][last]a1a_1a1表示可以涂1块木块的有多少种颜色以此类推lastlastlast表示上一次用的是可以涂lastlastlast个木块的颜色。
接下来就是考虑dp方程的转移了。 举个例子 假设上一次用的颜色是可以涂5个块的那么下一步的状态转移就会变成 suma1∗dp[a1−1][a2][a3][a4][a5][1]a2∗dp[a11][a2−1][a3][a4][a5][2]a3∗dp[a1][a21][a3−1][a4][a5][3](a4−1)∗dp[a1][a2][a31][a4−1][a5][4]a5∗dp[a1][a2][a3][a41][a5−1][5]sum a_1 * dp[a_1 - 1][a2][a3][a_4][a_5][1] a_2 * dp[a_1 1][a_2 - 1][a_3][a_4][a_5][2] a_3 * dp[a_1][a_2 1][a_3 - 1][a_4][a_5][3] (a4 - 1) * dp[a_1][a_2][a_3 1][a_4 - 1][a_5][4] a5 * dp[a_1][a_2][a_3][a_4 1][a_5 - 1][5]suma1∗dp[a1−1][a2][a3][a4][a5][1]a2∗dp[a11][a2−1][a3][a4][a5][2]a3∗dp[a1][a21][a3−1][a4][a5][3](a4−1)∗dp[a1][a2][a31][a4−1][a5][4]a5∗dp[a1][a2][a3][a41][a5−1][5]
之所以a4−1a_4 - 1a4−1是因为上一步选的是5所以转移过来的时候a41a_4 1a41这里面有一个是跟上一个块同颜色的所以需要减去其他情况同理。
考虑到数据比较小并且这个dp方程有点难转移因此我们可以考虑用记忆化搜索来进行dp转移。
代码
/*Author : lifehappy
*/
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include bits/stdc.h
#define mp make_pair
#define pb push_back
#define endl \nusing namespace std;typedef long long ll;
typedef unsigned long long ull;
typedef pairint, int pii;const double pi acos(-1.0);
const double eps 1e-7;
const int inf 0x3f3f3f3f;inline ll read() {ll f 1, x 0;char c getchar();while(c 0 || c 9) {if(c -) f -1;c getchar();}while(c 0 c 9) {x (x 1) (x 3) (c ^ 48);c getchar();}return f * x;
}void print(ll x) {if(x 10) {putchar(x 48);return ;}print(x / 10);putchar(x % 10 48);
}const int mod 1e9 7;ll dp[20][20][20][20][20][10];
int n, a[10];ll dfs(int a1, int a2, int a3, int a4, int a5, int last) {if(dp[a1][a2][a3][a4][a5][last]) return dp[a1][a2][a3][a4][a5][last];ll ans 0;if(a1) ans (ans 1ll * (a1 - (last 2)) * dfs(a1 - 1, a2, a3, a4, a5, 1)) % mod;if(a2) ans (ans 1ll * (a2 - (last 3)) * dfs(a1 1, a2 - 1, a3, a4, a5, 2)) % mod;if(a3) ans (ans 1ll * (a3 - (last 4)) * dfs(a1, a2 1, a3 - 1, a4, a5, 3)) % mod;if(a4) ans (ans 1ll * (a4 - (last 5)) * dfs(a1, a2, a3 1, a4 - 1, a5, 4)) % mod;if(a5) ans (ans 1ll * a5 * dfs(a1, a2, a3, a4 1, a5 - 1, 5)) % mod;return dp[a1][a2][a3][a4][a5][last] ans;
}int main() {// freopen(in.txt, r, stdin);// freopen(out.txt, w, stdout);// ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);n read();for(int i 1; i n; i) {int x read();a[x];}for(int i 1; i 5; i) dp[0][0][0][0][0][i] 1;print(dfs(a[1], a[2], a[3], a[4], a[5], 0));return 0;
}
