hdu 2546饭卡

时间:2022-09-02 14:05:42

用5块钱去买最贵的物品,用剩下的m-5块去买尽量多的物品

 #include<stdio.h>
#include<math.h>
#include<vector>
#include<stdlib.h>
#include<string.h>
#include<iterator>
#include<iostream>
#include<algorithm>
#include<set>
#include<map>
using namespace std; int dp[],cost[]; int main()
{
int n,money,max_cost;
while(scanf("%d",&n) && n!=)
{
memset(cost,,sizeof(cost));
memset(dp,,sizeof(dp));
for(int i=;i<=n;i++)
scanf("%d",&cost[i]);
scanf("%d",&money); sort(cost+,cost+n+); max_cost=cost[n]; if(money<)
printf("%d\n",money); else
{
for(int i=;i<n;i++) //----------注意是n-1因为最大的n已经取走
for(int j=money-;j>=cost[i];j--)
dp[j]=max(dp[j],dp[j-cost[i]]+cost[i]); printf("%d\n",money-max_cost-dp[money-]);
}
}
return ;
}