当前位置: 代码迷 >> 综合 >> 洛谷 P1855 榨取kkksc03 (二维费用背包)
  详细解决方案

洛谷 P1855 榨取kkksc03 (二维费用背包)

热度:103   发布时间:2023-09-20 19:12:03.0

加多一维就行了

#include<cstdio>
#include<algorithm>
#include<cstring>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;const int MAXN = 212;
int f[MAXN][MAXN], w1[MAXN], w2[MAXN];
int n, m, t;int main()
{scanf("%d%d%d", &n, &m, &t);REP(i, 0, n) scanf("%d%d", &w1[i], &w2[i]);REP(i, 0, n)for(int j = t; j >= w1[i]; j--)for(int k = m; k >= w2[i]; k--)f[j][k] = max(f[j][k], f[j-w1[i]][k-w2[i]] + 1);printf("%d\n", f[t][m]);return 0;
}