ztc.的平台

· · 个人记录

一个长度为n的正方形块，一共有两种颜色，每个块有一个颜色，相邻两行颜色要么完全相同要么完全不同，若一个平台中存在一个矩形中的方块全部为相同材质，且他的面积大于k，那么 不花里胡哨 ;

如果花里胡哨，则 ans++;

求 ans%P 的值.

每行输入三个数n,k,P

因为相邻两行必须完全相同或者完全不同，那么我们只需要求出第一行和第一列的颜色就可以求出整张图的颜色。

因为要求其中涂色相同的最大矩形面积小于k，所以对于第一行连续相同最长的涂色的长度乘上第一列连续相同最长的涂色的长度必须要小于k。

怎么求最长连续涂色个数的方案数呢：

求方案数-->Dynamic Programming

设DP状态 f[i][j][k]为长度为i，最长连续涂色数为k，尾部最长连续涂色为j的方案数。

分两种情况：

1.新的结尾的颜色和老的结尾的颜色相同。

f[i][j+1][max(k,j+1)]+=f[i][j][k]

2.新的结尾的颜色和老的结尾的颜色不同。

f[i+1][1][max(1,k)]+=f[i][j][k]

统计答案：

计算所有长度乘在一起小于k的方案数即可。

答案除2

这是一种 O(n^{2})做法。

由第一行和第一列可以确定一个漂亮的正方形，且最大的同色兹举行面积为首行和首列中最长同色子串的长度的乘积。

我们考虑一个 dp 计算一个 1*n 的方案数

令 f[i][j]表示前i个最长同色子串长度<=j的个数的情况数：

for(register int l=i-j;l<=i-1;l++) 
f[i][j]+=f[l][min(j,l)]
统计答案 先把$f[n][i]$减去$f[n][i-1]$使之成为$1*n$中最长同色子串刚好为$i$ 的情况数。 枚举$i,j$，如果乘积 $<k$ 那么就把 $f[n][i]*f[n][j]$统计入答案。