【洛谷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=101;
int f[MAX][2*MAX][2*MAX];
int M[MAX],T[MAX];
int n,m,t,ans=0;
int main()
{
       cin>>n>>m>>t;
       for(int i=1;i<=n;++i)
          cin>>M[i]>>T[i];
       for(int i=1;i<=n;++i)
         for(int j=m-M[i];j>=0;--j)
           for(int k=t-T[i];k>=0;--k)
              ans=max(ans,f[i][j][k]=max(f[i-1][j][k],f[i-1][j+M[i]][k+T[i]]+1));
       cout<<ans<<endl;
       return 0;  
}

诶诶诶
我去
怎么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=101;
int f[MAX][2*MAX][2*MAX];
int M[MAX],T[MAX];
int n,m,t,ans=0;
int main()
{
	   cin>>n>>m>>t;
	   for(int i=1;i<=n;++i)
	      cin>>M[i]>>T[i];
	   for(int i=1;i<=n;++i)
	     for(int j=m;j>=0;--j)
	       for(int k=t;k>=0;--k)
	         if(j+M[i]<=m&&k+T[i]<=t) 
	          ans=max(ans,f[i][j][k]=max(f[i-1][j][k],f[i-1][j+M[i]][k+T[i]]+1));
	         else
	          ans=max(ans,f[i][j][k]=f[i-1][j][k]);
	   cout<<ans<<endl;
	   return 0;  
}