自动搬运

查看原文

来自洛谷，原作者为

	林家三少 今天也是元气满满的一天哦qwq

搬运于2025-08-24 21:37:37，当前版本为作者最后更新于2019-12-13 13:32:47，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

蒟蒻刚学dp(没错就是这么蒻)，然后就看到了这道题，所以就有了这篇题解qwq

一开始我还不懂为什么要输入老王和$WKY$的水平值、老王做知识点$i$的时间，后来看了题解问了同学才知道，原来是：

通过老王和$WKY$的水平值和老王做知识点$i$的时间来求出$WKY$做知识点$i$的时间

如果我们只看$WKY$拥有时间、题目所属的知识点、题目对应的奖励值，然后求能到得到的最大奖励值，

然后这就变成了一道简单的$dp$题

所以现在当务之急就是求出$WKY$做各个知识点的时间

根据

如果WKY的水平值是1，老王的水平值是2，那么WKY做同一道题的时间就是老王的2倍。

这句话，还有

老王的水平值是WKY的水平值的整数倍。

这句话的保证，我们可以推出这个公式：

WKY做知识点i的时间=老王做知识点i的时间*(老王的水平值/WKY的水平值)

然后再把$dp$转移方程求出来：

$f[j]=max(f[j],f[j-t2[p[i]]]+q[i]);$

其中$t2[p[i]]$也就是$WKY$做第$i$道题的时间，因为$p[i]$是第$i$道题的知识点，而$t2[]$是$WKY$做知识点的时间，最后把完整代码附上：

#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std;
int a,b;
int n,m;
int t1[5000+10],t2[5000+10];
int t;
int p[5000+10],q[5000+10];
int f[5000+10];
//标准的dp数组
int main(){
	cin>>a>>b;
	cin>>m>>n;
	for(int i=1;i<=n;i++){
		cin>>t1[i];
		t2[i]=t1[i]*(b/a);
        //这里也就是根据老王做知识点i来求出WYK做知识点i的时间
	}
	for(int i=1;i<=m;i++){
		cin>>p[i]>>q[i];
        //开始输入知识点和奖励
	}
	cin>>t;
	for(int i=1;i<=m;i++){
		for(int j=t;j>=t2[p[i]];j--){
			f[j]=max(f[j],f[j-t2[p[i]]]+q[i]);
            //标准的dp转移方程
		}
	}
	cout<<f[t];
    //最后在输出答案
	return 0;
}

看在我打了那么多字的份上，点个赞再走吧