活动时间：7月7日起至9月1日
活动内容：写当日题解，活动时间内一共写满30篇每日一题的题解
活动奖励：即可额外获得牛客T恤一件
活动目的：滴滴滴～想充实的过完这个暑假嘛～快来写每日一题～每天都要进步喔～提升自己的同时还有超多福利喔～

每日一题交流群，群内定期有福利发放，群号：659028468

今日每日一题预告

题号 NC20265
名称 [SCOI2008]着色方案
来源 [SCOI2008]
戳我进入往期每日一题汇总贴~
往期每日一题二期题单



如果你在题库做题时遇到了喜欢的题目，欢迎推荐给邓老师~ 点击查看详情

题解

作为一个dp，想到一个合适的状态是一件很重要的事情，对于这一个题来说，这确实也是做dp最难的一点……对于百分之五十的数据，我们当然可以最简单的用f[i][j][k][l][m]表示每一种种颜色分别剩i,j,k,l,m个的方案数，但是还有百分之五十数据就没办法了……但是ACM又不是oi可以骗分。
再看看数据范围——ci是小于5的，这样的范围大概率都有提示意义，如果你对于数据范围很敏感，你就大概能够想到这样一个状态了：若每种颜色剩余能涂的木板数记为Ci那么f[a][b][c][d][e][last]表示C值为1的颜料有a种，C值为2的颜料有a种……最后一个格子颜色的C值是last！
所以：


（写成记忆化搜索的话转移方程会简洁一点，大家可以自行探索）

如果你对排列组合比较熟悉，还有一种方法：
f[i][j]为，用前i种颜色的所有颜料涂色，其中有j个相邻的颜色是一样，这个时候如果要加入一个颜色，即在前i种颜色的sum[i]（前缀和）个格子里面插入c[i+1]个第i+1种颜色的格子，插入的时候，我们让c[i+1]个格子分成x段，有C(c[i+1]-1,x-1)种划分方法（隔板法）。且***去的时候隔开了y个原来相同的格子，还是用隔板法——分开相邻的y个需要在j个相邻颜色一样的空位里面挑y个插入，剩下的则在剩下的sum[i]+1-j个位置里面挑x-y个位置插入。而这样一插，原来的相邻同色减少了y个，增加了c[i+1]-x个，所有j变成j-y+c[i+1]。（xy均需要循环枚举）
如果我们用C(i,j)表示组合数那么转移方程为：
最后的答案是f[n][0]

活动奖励：

在牛客博客中写出题解，并回复地址
审核通过可获得（依据题目难度和题解的内容而定）

本道题目7月27日中午12：00之前写的题解有获得牛币资格~

.牛币兑换中心

牛客博客开通方式

1. 如何开通牛客博客：https://www.nowcoder.com/discuss/202952
2. 如何使用博客搬家功能：进入博客--->设置--->底部博客搬家
3. 如果你对牛客博客有任何意见或建议：牛客博客意见反馈专贴