UC知道NOIP PASCAL 邮票面值设计问题
来源：百度知道 编辑：UC知道 时间：2024/09/21 08:08:21
给定一个信封，最多只允许粘贴N张邮票，计算在给定K（N+K≤40）种邮票的情况下（假定所有的邮票数量都足够），如何设计邮票的面值，能得到最大值MAX，使1…MAX在之间的每一个邮资值能得到。
例如：N=3，K=2，如果面值分别为1分、4分，则在1分…6分之间的每一个邮资值都能得到（当然还有8分、9分和12分）；如果面值分别为1分、3分，则在1分…7分之间的每一个邮资值都能得到。可以验证当N=3，K=2时，7分就是可以得到连续的邮资最大值，所以MAX=7，面值分别为1分、3分。
样例：INPUT N=3 K=2 OUPUT 1 3
首先，能用DP吗，我以为应该能的，不能还烦劳说明理由
其次，想法是怎么样的，复杂度多少
还有，怎么判断这道题该用什么办法
（请别直接贴程序，我都看毛了）
能具体点吗/
二楼，OIBH什么会员制度？注册了不让看啊
例如：N=3，K=2，如果面值分别为1分、4分，则在1分…6分之间的每一个邮资值都能得到（当然还有8分、9分和12分）；如果面值分别为1分、3分，则在1分…7分之间的每一个邮资值都能得到。可以验证当N=3，K=2时，7分就是可以得到连续的邮资最大值，所以MAX=7，面值分别为1分、3分。
样例：INPUT N=3 K=2 OUPUT 1 3
首先，能用DP吗，我以为应该能的，不能还烦劳说明理由
其次，想法是怎么样的，复杂度多少
还有，怎么判断这道题该用什么办法
（请别直接贴程序，我都看毛了）
能具体点吗/
二楼，OIBH什么会员制度？注册了不让看啊
我考虑从1开始枚举，对每个值做0-1背包。。看是否能被物品(面值)装满
这个题我觉得不能DP，但判断是要用到DP。
你看数据量，n+k<=40,一般来说DFS应该差不多，如果你的搜索结构好的话就能AC。
题解在OIBH上有，你自己去看吧