社区讨论
为什么对f_tim[]进行初始化是错的?
P1509找啊找啊找GF参与者 2已保存回复 3
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 3 条
- 当前快照
- 1 份
- 快照标识符
- @m2syqfk9
- 此快照首次捕获于
- 2024/10/28 19:56 去年
- 此快照最后确认于
- 2025/11/04 15:47 4 个月前
CPP
#include <bits/stdc++.h>
using namespace std;
#define oo 2147483648ll
typedef long long ll;
typedef pair<ll, ll> pll;
const ll N = 2e2 + 5, M = 1e4 + 5, mod = 7;
ll n, m, r, rmb[N], tim[N], rp[N], f_tim[N][N], f_num[N][N];
void solve()
{
cin >> n;
for (ll i = 1; i <= n; i++)
cin >> rmb[i] >> rp[i] >> tim[i];
cin >> m >> r;
// memset(f_tim, 0x3f, sizeof(f_tim));
// f_tim[0][0] = 0;//加上这两句话就错了,为什么?
for (ll i = 1; i <= n; i++)
{
for (ll j = m; j >= rmb[i]; j--)
{
for (ll k = r; k >= rp[i]; k--)
{
if (f_num[j][k] < f_num[j - rmb[i]][k - rp[i]] + 1)
{
f_tim[j][k] = f_tim[j - rmb[i]][k - rp[i]] + tim[i];
f_num[j][k] = f_num[j - rmb[i]][k - rp[i]] + 1;
}
else if (f_num[j][k] == f_num[j - rmb[i]][k - rp[i]] + 1)
f_tim[j][k] = min(f_tim[j][k], f_tim[j - rmb[i]][k - rp[i]] + tim[i]);
}
}
}
cout << f_tim[m][r] << endl;
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
ll TTT = 1;
// cin >> TTT;
while (TTT--)
{
solve();
}
return 0;
}
回复
共 3 条回复,欢迎继续交流。
正在加载回复...