天天看點

題解 P1855 【榨取kkksc03】CODE

盡管說這是站長大人出的題,但确實很簡單。->_->

這就是一個二維背包費用問題,用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]);
}