#652 实现愿望

题意

这是一个经典的二位费用背包模板题，考虑dp。
两个费用分别是$m$金钱和$t$时间

DP

定义

我们来设计一下状态，dp[j][k]表示在花费$j$元金钱和$t$时间的情况下，能够实现的最多的愿望个数

状态转移

对于每一个愿望$i$，倒序循环遍历 $M$ ~ $m_i$，$T$ ~ $t_i$。
计算dp[j][k]=max(dp[j][k],dp[j-m[i]][k-t[i]]+1)

输出

最终输出dp[M][T]。

代码

//flpar
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rg register
const int N=205;
void init();
int n,M,T;
int m[N>>1],t[N>>1],dp[N][N];
signed main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	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>=m[i];j--)
			for(int k=T;k>=t[i];k--)
				dp[j][k]=max(dp[j][k],dp[j-m[i]][k-t[i]]+1);
	cout<<dp[M][T];
	return 0;
}
void init(){
	
	return ;
}