题解 P1855 【榨取kkksc03】

本文主要是介绍题解 P1855 【榨取kkksc03】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

尽管说这是站长大人出的题，但确实很简单。->_->

这就是一个二维背包费用问题，用dp[i][j]表示当钱为i，时间为j时能最大满足愿望数量；

那么状态转移方程为：dp[j][k]=max(dp[j][k],dp[j-mon[i]][k-tim[i]]+1)；

CODE

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=205;
int dp[N][N],n,m,summ,sumt,mon[N],tim[N];
int main()
{scanf("%d%d%d",&n,&summ,&sumt);for(int i=1;i<=n;i++){scanf("%d%d",&mon[i],&tim[i]);}for(int i=1;i<=n;i++)for(int j=summ;j>=mon[i];j--)for(int k=sumt;k>=tim[i];k--){dp[j][k]=max(dp[j][k],dp[j-mon[i]][k-tim[i]]+1);//状态转移方程}printf("%d",dp[summ][sumt]);
}

这篇关于题解 P1855 【榨取kkksc03】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---