洛谷p1855 榨取kkksc03

P1855 榨取kkksc03

  一道01背包模板题,但多了一个维度。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

#include <cstdio>
#include <cstring>
using namespace std;
int m[205],t[205];
int dp[205][205];
int ()
{

#include <cstdio>
#include <cstring>
using namespace std;
int m[205],t[205];
int dp[205][205];
int ()
{
int n,M,T;
cin>>n>>M>>T;
memset(m,0,sizeof(m));
memset(t,0,sizeof(t));
memset(dp,0,sizeof(dp));
for(int i=0;i<n;i++)
cin>>m[i]>>t[i];
int ans=-1;
for(int k=0;k<n;k++){
for(int i=M;i>=m[k];i--){
for(int j=T;j>=t[k];j--){
dp[i][j]=max(dp[i][j],dp[i-m[k]][j-t[k]]+1);
}
}
}
cout<<dp[M][T]<<endl;
return 0;
}
}