本文从WordPress迁移而来, 查看全部WordPress迁移文章
hdu 2604 queuing
dp,矩阵
题意:有男女,用mf表示,给出人数L,队长为L的队伍,有2^L中排队方法,包含fmf,fff的为O序列,否则为E序列,需要统计E序列有多少个
这种线性序列,又统计的,一般都是用dp的思维是思考
定义dp[i]为长度为i的队列中包含多少个E序列
- 如果第i位填m,那么不会产生什么影响,直接继承 dp[i] += dp[i-1]
如果第i位填f,那么(i-2,i-1)位,不能填ff,fm,只能填mf,mm,讨论
- 如果(i-2,i-1)填mm,那么对于i-3以前的串也没什么影响,所以直接继承 dp[i] += dp[i-3]
如果(i-2,i-1)填mf,那么i-3只能填m,不能填f,如果i-3填m,可以不对跟i-4产生什么影响(和 1. 一样的道理),所以直接继承dp[i] += dp[i-4]
总结 dp[i] = dp[i-1] + dp[i-3] + dp[i-4]
这是个线性方程,可以构造个矩阵来解;
直接解,O(n),数据太大承受不了
构造矩阵,老套路,就不说了,不过先算出dp[0],dp[1],dp[2],dp[3],dp[4]
1 |
|
hdu 1757 A Simple Math Problem
简单题
1 |
|
hdu 2256 Problem of Precision
按照题意,打表,观察规律,很容易看到规律
fn = 10*fn-1 - fn-2 + 8
构造矩阵,求即可
这题修复了模板中的bug,像这题,矩阵里面有些元素是负数
在取模的时候要对负数有所处理
1 | /* |
hdu 2294 Pendant
dp,矩阵
题意:有k种珠子,每种珠子都有n个,将这些珠子串成长度 <= n 的串,且必须包含k种颜色的珠子,有多少种串法
- n < k , 无解,0种
- dp[i][j]:i个珠子,用了j种颜色,有多少种串法, 状态转移方程: dp[i][j] = dp[i-1][j]j + dp[i-1][j-1](k-j+1)
- 要求的是长度 <= n 的所以解法,ans = dp[k][k] + dp[k+1][k] + dp[k+2][k] …… + dp[n][k]
- 考虑怎么得到dp数组,因为n太大了,可以用矩阵优化
( dp[k][k] , dp[k][k-1] , dp[k][k-2] , ……. , dp[k][1] )
得到
( dp[k+1][k] , dp[k+1][k-1] , dp[k+1][k-2] , dp[k+1][k-3] , ……. , dp[k+1][1] )
构造一个 k k 的矩阵就可以了,上矩阵 k阶矩阵 = 下矩阵
对于到得到任意的 dp[i][k] 是比较简单的
但是要求的是 ans = dp[k][k] + dp[k+1][k] + dp[k+2][k] …… + dp[n][k]
不妨为
s[k] = d[k][k]
s[k+1] = s[k] + dp[k+1][k+1]
……….
s[n] = s[n-1] + dp[n][k]
答案就是 s[n]
怎么求s[n]呢,把s[k]放进去上面的矩阵就可以了
( 0 , dp[k][k] , dp[k][k-1] , dp[k][k-2] , ……. , dp[k][1] )
得到
( s[k] , dp[k+1][k] , dp[k+1][k-1] , dp[k+1][k-2] , dp[k+1][k-3] , ……. , dp[k+1][1] )
把k阶矩阵,扩展为k+1阶矩阵即可,不难嘛
最后求得
( s[n-1] , dp[n][k] , dp[n][k-1] , dp[n][k-2] , dp[n][k-3] , ……. , dp[n][1] )
答案 = s[n-1] + dp[n][k]
1 |
|
hdu 2276 Kiki & Little Kiki 2
一个灯它下一秒的状态只与它左边的灯有关,可以找到一个公式来描述这种变化
a[i] = (a[i] 1 + a[(i - 1 + n) % n] 1) % 2
基于这个变化的公式,可以构建一个矩阵,初始状态乘上n次这个矩阵,就是变化n次,要知道n秒后的状态,做矩阵快速幂即可
1 |
|