HDU 5642 King's Order(數位DP)
題意:要求你生成一個合法的字符串, 由小寫字母a~z組成, 相同字母相鄰出現不能超過3個, 求有多少種組合。
思路:數位DP來做, 用d[i][j][k]表示處理完前i個字母, 第i-1個字母為j,已經連續出現了k次的方法數。 然後每次轉移就很簡單了, 繼續選擇字母j(if(k < 3)), 或者換其他的。
細節參見代碼:
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include