杭电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[...
