算法设计与分析勇者斗恶龙;挖隧道问题;消消乐问题;Shacozzz的生财之道;蜘蛛纸牌
在很久很久以前，地上有一个荣光的王国，在这个王国里，国民安居乐业，国王开明勤政。但是突然有一天，有一群恶龙入侵了这个美丽的国家。恶龙们一路杀到了这个国家的首都，王国岌岌可危。在这个生死攸关的时刻，王国的总共 n个勇者们聚集到了首都，在他们当中第 i个勇者的能力值为 ai ,这代表这个勇者能够对恶龙造成 ai点伤害或者防御住恶龙 ai 的攻击。与此同时，王国的勇士们获得了恶龙们的情报：在城外总共有 m条恶龙，第 i条恶龙的防御力为 xi ，攻击力为 yi。幸运的是，恶龙们每次只会有一条来进攻首都。并且进攻的顺序为 1到 m.为了守住城堡，勇士们开始商量策略:保险起见，勇士们决定每次只派一个勇士出去击杀恶龙，剩下的勇士们将留在城堡中守护首都。为了守住首都，出门迎战的勇士的能力值不能小于恶龙的防御力。而剩下的在首都的城堡里防御的勇士们的能力值之和不能小于恶龙的攻击力。与此同时，国王拿出了一种神奇的药水（数量无限多），每一瓶药水能够让勇士的能力值短暂的提升 1点，药效只能保证勇士们应对一条恶龙，由于神奇药水的效果可以叠加（一个勇士可以同时喝 k瓶药增加 k 点能力值）以及药水数量无限，我们就能