?

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

題意:打怪,還有最后一級，忍耐度有限m,問在殺怪數(shù)量上限為s的情況下能否獲取n經(jīng)驗而通關，且忍耐度花越少越好。

分析：dp[i][j]表示打了數(shù)量為i花費忍耐度為j得到的最大經(jīng)驗值。

狀態(tài)轉(zhuǎn)移方程：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[110][110],w[110],p[110]; int main() {int n,m,s,k;while(scanf("%d%d%d%d",&n,&m,&k,&s)>0){for(int i=1;i<=k;i++)scanf("%d%d",&p[i],&w[i]);memset(dp,-1,sizeof(dp));memset(dp[0],0,sizeof(dp[0]));for(int i=1;i<=k;i++)for(int j=w[i];j<=m;j++)for(int k=s;k>0;k--){if(dp[k-1][j-w[i]]!=-1)dp[k][j]=max(dp[k][j],dp[k-1][j-w[i]]+p[i]);}int ans=-1;for(int i=1;i<=s;i++)for(int j=1;j<=m;j++)if(dp[i][j]>=n){ans=max(ans,m-j);break;}printf("%d\n",ans);} } View Code

?

轉(zhuǎn)載于:https://www.cnblogs.com/lienus/p/4151450.html

總結(jié)

以上是生活随笔為你收集整理的hdu2159（二维完全背包）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。