hdu2159（二维完全背包）

时间：2024-01-21 19:13:03

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2159

题意:打怪,还有最后一级，忍耐度有限m,问在杀怪数量上限为s的情况下能否获取n经验而通关，且忍耐度花越少越好。

分析：dp[i][j]表示打了数量为i花费忍耐度为j得到的最大经验值。

状态转移方程：dp[i][j]=max(dp[i][j],dp[i-1][j-w[i]]+p[i])

#include <cstdio>

#include <cstring>

#include <cmath>

#include <iostream>

#include <algorithm>

#include <queue>

#include <cstdlib>

#include <vector>

#include <set>

#include <map>

#define LL long long

#define mod 1000000007

#define inf 0x3f3f3f3f

#define N 10010

using namespace std;

int dp[][],w[],p[];

int main()

{

    int n,m,s,k;

    while(scanf("%d%d%d%d",&n,&m,&k,&s)>)

    {

        for(int i=;i<=k;i++)scanf("%d%d",&p[i],&w[i]);

        memset(dp,-,sizeof(dp));

        memset(dp[],,sizeof(dp[]));

        for(int i=;i<=k;i++)

        for(int j=w[i];j<=m;j++)

        for(int k=s;k>;k--)

        {

            if(dp[k-][j-w[i]]!=-)

            dp[k][j]=max(dp[k][j],dp[k-][j-w[i]]+p[i]);

        }

        int ans=-;

        for(int i=;i<=s;i++)

        for(int j=;j<=m;j++)

        if(dp[i][j]>=n)

        {

            ans=max(ans,m-j);break;

        }

        printf("%d\n",ans);

    }

}

相关文章