80分求调整
查看原帖
80分求调整
1153156
Elysium_Guiwow楼主2024/7/18 08:15

最后两个点TLE了

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define ri register int
#define ld long double
#define ii inline int
#define iv inline void
#define ib inline bool
#define il inline ll
#define is inline string
#define ci const int
#define vi vector<int>
#define pq prioritb_queue
#define di deque<int>
#define pr pair<int, int>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define inf 0x3f3f3f3f
#define infll 0x3f3f3f3f3f3f3f3f
#define mod 1000000007
#define N 100010
int dp[N], v[N], w[N], cnt;
signed main()
{
    int n, W;
    int a, b, m;
    cin >> n >> W;
    for (ri i = 1; i <= n; ++i)
    {
        cin >> a >> b >> m;
        for (ri j = 1; j <= m; ++j)
        {
            ++cnt;
            v[cnt] = a;
            w[cnt] = b;
        }
    }
    for (ri i = 1; i <= cnt; ++i)
        for (ri j = W; j >= w[i]; --j)
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]); 
    cout << dp[W];
}
2024/7/18 08:15
加载中...