题解 P2430 【严酷的训练】

· · 题解

蒟蒻刚学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;
}

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