10313专题

UVA - 10313 Pay the Price

题意:在1-300之间,给你n,如果后面没跟着数字,代表用1-n的的种数凑成n,如果有一个数的话代表用1-l1种数凑成n,如果还有l2,代表用种数大于l1,小于l2的数凑成n,这貌似没思路啊,枚举的话好像不是太可能啊,后来看到这题涉及到一个结论ferrers图的性质:数n拆分成k个数的和的拆分数,和数n拆分成最大数为k的拆分数相等,然后就用 dp[i][j]代表用大小不超过j的数凑成i的方法个数