杭电ACM——2546,饭卡(DP)
一维背包问题。突破口:将菜的价格从小到大排序,对前n-1个物品进行DP,找出消费金额不超过m-5的方案中最大的消费金额sum,在此基础上,m - (sum+price[n]) 即为卡内最小余额。因此,我们DP应在余额为0~m-5之内找出最优的解。状态:dp[i,j]为在前i种菜中,当余额为j时,所能进行的最大消费。状态转移方程:dp[i,j]=if(j<price[i]) dp[...