In this game, there is a technology tree system. There are n kinds of technology in this game, each of them has m levels numbered from 1 to m. In the beginning, all technologies have no level . When the i-th technology is at the -th level, the player can pay. pokedollars to upgrade this technology into the j-th level. However, sometimes upgrading is so easy that the cost might be negative, which implies the player may gain profit from upgrading technologies.Moreover, if all technologies have been upgraded to level j, the player will gain an additional profit of. pokedollars. However, sometimes too many technologies of the same level might be confusing, hence the profit can be negative as well.Rowlet wants to determine the optimal strategy that can bring him the most pokedollars. Help him to find the maximum gain. Note that Rowlet may upgrade nothing, and in that case, the profit is zero.
Rowlet is playing a very popular game in the pokemon world. Recently, he has encountered a problem and wants to ask for your help. In this game, there is a technology tree system. There are n kinds of technology in this game, each of them has m levels numbered from 1 to m. In the beginning, all technologies have no level (regard as level 0). When the i-th technology is at the (j - 1)-th level, the player can pay c_{i j} c ij pokedollars (currency used in this game) to upgrade this technology into the j-th level. However, sometimes upgrading is so easy that the cost might be negative, which implies the player may gain profit from upgrading technologies. Moreover, if all technologies have been upgraded to level j, the player will gain an additional profit of d_{j} d j pokedollars. However, sometimes too many technologies of the same level might be confusing, hence the profit can be negative as well. Rowlet wants to determine the optimal strategy that can bring him the most pokedollars. Help him to find the maximum gain. Note that Rowlet may upgrade nothing, and in that case, the profit is zero.
标签： HBC52009Conspicuousness 字符串 后缀自动机(SAM) 动态规划Upgrading Technology题解
