【洛谷1855】 榨取kkksc03

題面

前面省去一堆背景内容

洛谷的營運組決定，如果一名oier向他的教練推薦洛谷，并能夠成功的使用（成功使用的定義是：該團隊有20個或以上的成員，上傳10道以上的私有題目，布置過一次作業并成功舉辦過一次公開比賽），那麼他可以浪費掉kkksc03的一些時間的同時消耗掉kkksc03的一些金錢以滿足自己的一個願望。

Kkksc03的時間和金錢是有限的，是以他很難滿足所有同學的願望。是以他想知道在自己的能力範圍内，最多可以完成多少同學的願望？

輸入格式：

第一行,n M T，表示一共有n(n<=100)個願望，kkksc03 的手上還剩M(M<=200)元，他的暑假有T(T<=200)分鐘時間。

第2~n+1行 mi,ti 表示第i個願望所需要的時間和金錢。

輸出格式：

一行，一個數，表示kkksc03最多可以實作願望的個數。

輸入樣例#1：

6 10 10

1 1

2 3

3 2

2 5

5 2

4 3

輸出樣例#1：

4

題解

這道題目。。

看着題目，就知道是一道DP的題目吧，。。。

很明顯的01背包的題目

直接使用背包去接就行了

01背包，上~~

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
//f[i][j][k]表示前i個願望，剩餘j元錢，k時間的最多實作願望數 
const int MAX=;
int f[MAX][*MAX][*MAX];
int M[MAX],T[MAX];
int n,m,t,ans=;
int main()
{
       cin>>n>>m>>t;
       for(int i=;i<=n;++i)
          cin>>M[i]>>T[i];
       for(int i=;i<=n;++i)
         for(int j=m-M[i];j>=;--j)
           for(int k=t-T[i];k>=;--k)
              ans=max(ans,f[i][j][k]=max(f[i-][j][k],f[i-][j+M[i]][k+T[i]]+));
       cout<<ans<<endl;
       return ;  
}
           

嗯嗯嗯代碼真簡短

真容易

诶诶诶

我去

怎麼WA了！！！

咔咔咔

什麼鬼

怎麼可能會WA

一臉懵逼

不科學呀！！！

恩恩

仔細想一想

這裡隻考慮了能夠選擇的時候的最大值。。。

如果目前這個不能夠選擇的話。。。。

那麼f[i][j][k]就變成0了。。。。

哦

改一改就好了

↓正解

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
//f[i][j][k]表示前i個願望，剩餘了j元錢，k時間的最多實作願望數 
const int MAX=;
int f[MAX][*MAX][*MAX];
int M[MAX],T[MAX];
int n,m,t,ans=;
int main()
{
       cin>>n>>m>>t;
       for(int i=;i<=n;++i)
          cin>>M[i]>>T[i];
       for(int i=;i<=n;++i)
         for(int j=m;j>=;--j)
           for(int k=t;k>=;--k)
             if(j+M[i]<=m&&k+T[i]<=t) 
              ans=max(ans,f[i][j][k]=max(f[i-][j][k],f[i-][j+M[i]][k+T[i]]+));
             else
              ans=max(ans,f[i][j][k]=f[i-][j][k]);
       cout<<ans<<endl;
       return ;  
}