首页 > 代码库 > [SCOI2008] 着色方案[高维dp]
[SCOI2008] 着色方案[高维dp]
321. [SCOI2008] 着色方案
★★★ 输入文件：color.in 输出文件：color.out 简单对比
时间限制：1 s 内存限制：64 MB
题目背景：
有n个木块排成一行，从左到右依次编号为1~n。你有k种颜色的油漆，其中第i 种颜色的油漆足够涂ci 个木块。所有油漆刚好足够涂满所有木块，即 c1+c2+...+ck=n。相邻两个木块涂相同色显得很难看，所以你希望统计任意两个相邻木块颜色不同的着色方案。
【输入】
第一行为一个正整数k，第二行包含k个整数c1, c2, ... , ck。
【输出】
输出一个整数，即方案总数模1,000,000,007的结果。
【样例】
| 输入 | 输出 |
| 3 1 2 3 | 10 |
| 5 2 2 2 2 2 | 39480 |
| 10 1 1 2 2 3 3 4 4 5 5 | 85937576 |
【数据规模】
50%的数据满足：1 <= k <= 5, 1 <= ci <= 3
100%的数据满足：1 <= k <= 15, 1 <= ci <= 5
#include<cstdio>#include<cstring>using namespace std;typedef long long ll;const ll mod=1e9+7;const int N=16;int n,s[6];ll f[N][N][N][N][N][6];ll dfs(int a,int b,int c,int d,int e,int x){ ll &res=f[a][b][c][d][e][x],ans=0; if(a+b+c+d+e==0) return res=1; if(~res) return res; if(a) ans+=(a-(x==2))*dfs(a-1,b,c,d,e,1),ans%=mod; if(b) ans+=(b-(x==3))*dfs(a+1,b-1,c,d,e,2),ans%=mod; if(c) ans+=(c-(x==4))*dfs(a,b+1,c-1,d,e,3),ans%=mod; if(d) ans+=(d-(x==5))*dfs(a,b,c+1,d-1,e,4),ans%=mod; if(e) ans+=e*dfs(a,b,c,d+1,e-1,5),ans%=mod; return res=ans;}int main(){ freopen("color.in","r",stdin); freopen("color.out","w",stdout); memset(f,-1,sizeof f); scanf("%d",&n); for(int i=1,x;i<=n;i++) s[scanf("%d",&x),x]++; printf("%lld\n",dfs(s[1],s[2],s[3],s[4],s[5],0)); return 0;}
[SCOI2008] 着色方案[高维dp]
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。