FOJ 2126的解题思路,该怎么解决
FOJ 2126的解题思路
福大OJ上的一道题 http://acm.fzu.edu.cn/problem.php?pid=2126
哪位大神能给个解题思路？？（据说好像跟动态规划有关）
（能有个伪代码或代码当然是更好了。。）
------解决方案--------------------
和srm 484 div1 level2基本一样。
只是srm484中的题目相当于该oj上n=0的情况。
先看n=0怎么解：
添加一个颜色时，就在一个假想的栈中同时添加k-1个元素，表示将来这k-1个元素是要处理的。
用dp[i][j]表示有i种颜色需要消除，而对应的栈中有j个元素的状态。
来看状态转移：
j != 0时
一种做法是从假想栈中取出第一个元素，这个时候需要消除的颜色数不变，假想栈中的元素减少：
dp[i][j-1] += dp[i][j];要注意这里i没变，所以在状态转移时需要j从大到小。
另一种做法是从额外添加一个和当前栈顶元素不同的颜色，这样需要消除的颜色数加1，假想栈中的元素增加k-1：
dp[i+1][j+k-1] += (h-1)*dp[i][j];
而j==0时
任意添加元素，需要消除的颜色数加1，而假想栈中的元素增加k-1:
dp[i+1][j] += h * dp[i][j];
对于foj的题目首先知道一些必要条件：
n + m要被k整除，否则结果为0；
根据已有的n个元素，计算出假想栈中的元素个数，如果元素个数超了m，则结果为0；
设这n个元素有a种颜色，栈想栈中有b个元素，则令：
dp[a][b] = 1;其它元素为0.
最后
dp[a+(m-b)/k][0]为所求。
而显然，这里a没起作用，直接不求a，置0即可。
福大OJ上的一道题 http://acm.fzu.edu.cn/problem.php?pid=2126
哪位大神能给个解题思路？？（据说好像跟动态规划有关）
（能有个伪代码或代码当然是更好了。。）
------解决方案--------------------
和srm 484 div1 level2基本一样。
只是srm484中的题目相当于该oj上n=0的情况。
先看n=0怎么解：
添加一个颜色时，就在一个假想的栈中同时添加k-1个元素，表示将来这k-1个元素是要处理的。
用dp[i][j]表示有i种颜色需要消除，而对应的栈中有j个元素的状态。
来看状态转移：
j != 0时
一种做法是从假想栈中取出第一个元素，这个时候需要消除的颜色数不变，假想栈中的元素减少：
dp[i][j-1] += dp[i][j];要注意这里i没变，所以在状态转移时需要j从大到小。
另一种做法是从额外添加一个和当前栈顶元素不同的颜色，这样需要消除的颜色数加1，假想栈中的元素增加k-1：
dp[i+1][j+k-1] += (h-1)*dp[i][j];
而j==0时
任意添加元素，需要消除的颜色数加1，而假想栈中的元素增加k-1:
dp[i+1][j] += h * dp[i][j];
对于foj的题目首先知道一些必要条件：
n + m要被k整除，否则结果为0；
根据已有的n个元素，计算出假想栈中的元素个数，如果元素个数超了m，则结果为0；
设这n个元素有a种颜色，栈想栈中有b个元素，则令：
dp[a][b] = 1;其它元素为0.
最后
dp[a+(m-b)/k][0]为所求。
而显然，这里a没起作用，直接不求a，置0即可。