HDU 2546 饭卡 01背包变形

题目大意：中文题就不多说了

题目思路：由题意可知，只要高于5元，就可以随便刷，那我们就把最贵的留在最后刷。但是如果低于5元就什么也不能刷（哪怕你要买的物品价格不足五元），所以我们可以先求出（n-5）元的情况下最多能花掉多少钱，最后再减去最贵的物品价格就可以了，具体看代码吧。

#include<cstdio>
#include<stdio.h>
#include<cstdlib>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
#define INF 0x3f3f3f3f
#define MAX 1000005

using namespace std;

int dp[MAX],v[MAX],sum,ans;

void Init()
{
    sum=0;
    memset(dp,0,sizeof(dp));
}

int main()
{
    int n,m,i,j;

    while(scanf("%d",&n),n)
    {
        Init();

        for(i=1;i<=n;i++)
        {
            scanf("%d",&v[i]);

            sum+=v[i];
        }

        scanf("%d",&m);

        if(m < 5)//特判一下，因为不足五元你什么也买不到
        {
            printf("%d
",m);
            continue;
        }

        sort(v+1,v+1+n);//从小到大排序，方便得到最大值。

        for(i=1;i<n;i++)
        {
            for(j=m-5;j>=v[i];j--)
            {
                dp[j]=max(dp[j],dp[j-v[i]]+v[i]);//dp[i][j]表示在i件物品j元的条件下最多能花多少，明显dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i]]+v[i])，当前状态只和上一轮状态有关，所以可以压缩成一维数组
            }
        }

        int ans=m-dp[m-5]-v[n];

        printf("%d
",ans);
    }
    return 0;
}

View Code

HDU 2546 饭卡 01背包变形

相关推荐