【每日一题】7月20日题目精讲—着色方案

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

$\color{#FFD700}{【特别介绍】}$
每日一题交流群，群内定期有福利发放，群号：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[a][b][c][d][e][1] = f[a-1][b][c][d][e][1] \times a + f[a+1][b-1][c][d][e][2] \times b + f[a][b+1][c-1][d][e][3] \times c + f[a][b][c+1][d-1][e][4] \times d + f[a][b][c][d+1][e-1][5] \times e$
$f[a][b][c][d][e][2] = f[a-1][b][c][d][e][1] \times (a - 1) + f[a+1][b-1][c][d][e][2] \times b + f[a][b+1][c-1][d][e][3] \times c + f[a][b][c+1][d-1][e][4] \times d + f[a][b][c][d+1][e-1][5] \times e$
$f[a][b][c][d][e][3] = f[a-1][b][c][d][e][1] \times a + f[a+1][b-1][c][d][e][2] \times (b-1) + f[a][b+1][c-1][d][e][3] \times c + f[a][b][c+1][d-1][e][4] \times d + f[a][b][c][d+1][e-1][5] \times e$
（写成记忆化搜索的话转移方程会简洁一点，大家可以自行探索）

如果你对排列组合比较熟悉，还有一种方法：
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[i+1][j-y+c[i+1]-x]+=C[c[i+1]-1][x-1]\times f[i][j] \times C[j][y] \times C[sum[i]+1-j][x-y]$
最后的答案是f[n][0]

【每日一题】7月20日题目精讲—着色方案

题解

活动奖励：

牛客博客开通方式

全站热榜