虽然历经波折,但是这道题还是解得比较成功的一道题
有一种很很强烈的感觉,这到是简单题,于是不断地想各种方法解出来
一拿到题我就用直接模拟的方法,但是很容易就出错了
发现如果要完整一点的话就得用DFS了,但是很容易TLE了
后来我想了很多种方法去优化我的DFS----未果
最后一次我HASH都用上了,但是TLE得很惨烈.(下续)
HDOJ 2546饭卡 http://acm.hdu.edu.cn/showproblem.php?pid=2546
Problem Description
电子科大本部食堂的饭卡有一种很诡异的设计，即在购买之前判断余额。如果购买一个商品之前，卡上的剩余金额大于或等于5元，就一定可以购买成功（即使购买后卡上余额为负），否则无法购买（即使金额足够）。所以大家都希望尽量使卡上的余额最少。
某天，食堂中有n种菜出售，每种菜可购买一次。已知每种菜的价格以及卡上的余额，问最少可使卡上的余额为多少。
Input
多组数据。对于每组数据：
第一行为正整数n，表示菜的数量。n<=1000。
第二行包括n个正整数，表示每种菜的价格。价格不超过50。
第三行包括一个正整数m，表示卡上的余额。m<=1000。
n=0表示数据结束。
Output
对于每组输入,输出一行,包含一个整数，表示卡上可能的最小余额。
Sample Input
1
50
5
10
1 2 3 2 1 1 2 3 2 1
50
0
Sample Output
-45
32
(续上)
这都不行的话那只有DP了,我的DP很弱,但是后来的一次专题训练让我开了点窍
于是我翻出以前的DP总结出来看,便有了灵感:
这得利于我之前就把题目的化解为求一组的子序列和<=m-5的数里的最大数
听起来很费劲,但是如果要表达得更好恐怕不是一句话可以解决的
求解模型: 求序列的最大上升序列
经典的例题可以访问:
http://blog.csdn.net/jqandjq/archive/2009/02/26/3940712.aspx
具体方法:
建另一个数组.来记录每一遍历到的数的最优情况.
下面是我的代码,于由是从DFS的代码改过来的,所以有一些冗余的部分.