题目链接 Problem Description 可怜的公主在一次次被魔王掳走一次次被骑士们救回来之后,而今,不幸的她再一次面临生命的考验。魔王已经发出消息说将在T时刻吃掉公主,因为他听信谣言说吃公主的肉也能长生不老。年迈的国王正是心急如焚,告招天下勇士来拯救公主。不过公主早已习以为常,她深信智勇的骑士LJ肯定能将她救出。 现据密探所报,公主被关在一个两层的迷宫里,迷宫的入口是S(0,0
传送门:洛谷 解题思路: 不难看出是一道完全背包题,但是因为数据范围较大,所以背包方法是不可做的. 考虑使用生成函数的方法来解这道题. 不难写出每一个物品的生成多项式: 1 + x v i + x 2 ∗ v i + . . . + x ∞ ∗ v i 1+x^{vi}+x^{2*vi}+...+x^{\infty*vi} 1+xvi+x2∗vi+...+x∞∗vi 这是一道经典式子,我