「求助！！！（悬关）！」

求助！！！（悬关）！

板块学术版
楼主cmy20110301
当前回复6
已保存回复6
发布时间2023/7/31 12:49
上次更新2023/11/3 06:46:28

查看原帖

被骇客银狼阻止的越权访问保存失败

求助！！！（悬关）！

cmy20110301楼主2023/7/31 12:49

小奇采药

Description

小奇是只天资聪颖的喵，他的梦想是成为世界上最伟⼤的医师。

为此，他想拜喵星球最有威望的医师为师。

医师为了判断他的资质，给他出了⼀个难题。

医师把他带到⼀个到处都是草药的⼭洞里对他说：“小奇，这个⼭洞里有⼀些不同的草药，采每⼀株都需要⼀些时间，每⼀株也有它自身的价值。

我会给你⼀段时间，在这段时间里，你可以采到⼀些草药。

如果你是⼀只聪明的喵，你应该可以让采到的草药的总价值最⼤。

Format

Input

第 R ⾏包括 R 个整数 h ，表示数据组数。

对于每组数据，第 R ⾏包括 k 个整数，M ，K ，表示草药的数目和能用于采药的时间。

接下来 M ⾏，每⾏两个整数 ti, vi。

保证 m, ti, vi 在限制范围内均匀随机⽣成。

Output

输出 h ⾏，每⾏ R 个数字，表示每组数据答案。

Limitation

对于 30W 数据，1 ≤ n ≤ 20, 1 ≤ m, vi, ti ≤ 104

对于 60W 数据，1 ≤ n ≤ 100, 1 ≤ m, vi, ti ≤ 105

对于 100W 数据，1 ≤ T ≤ 10, 1 ≤ n ≤ 150, 1 ≤ m, vi, ti ≤ 10^9

Samples

输入数据 1

输出数据 1

输入数据 2

输出数据 2

本人代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
int t,m,f[1000005],w[1000005],v[1000005];
signed main()
{
    int H;
    cin>>H;
    while(H--) 
	{
        cin>>m>>t;
        for(int i=1;i<=m;i++)
             >>w[i]>>v[i];
        for(int i=1;i<=m;i++)
        {
            for(int j=t;j>=w[i];j--)
                f[j]=max(f[j],f[j-w[i]]+v[i]);
        }
        cout<<f[t]<<endl;
        memset(f,0,sizeof(f));
        memset(w,0,sizeof(w));
        memset(v,0,sizeof(v));
    }
    return 0;
}

只打了60分，RE了4个点。。。

2023/7/31 12:49