题解 P2430 【严酷的训练】
树下
2018-04-02 17:59:28
# 实际上是一个转化的01背包
## 将老王的水平除一下就会得到WKY的水平
### 之后再把知识点转化为v[i]就好了
```
#include<bits/stdc++.h>
using namespace std;
int s,ss,n,m,ans,num,t;
int c[5005],v[5005],w[5005],dp[5005];
int main(){
scanf("%d%d%d%d",&s,&ss,&m,&n);
ans=ss/s;
for(int i=1;i<=n;i++)
scanf("%d",&c[i]),c[i]*=ans;
for(int i=1;i<=m;i++)
scanf("%d%d",&num,&v[i]),w[i]=c[num];
scanf("%d",&t);
for(int i=1;i<=m;i++)
for(int j=t;j>=w[i];j--)
dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
printf("%d",dp[t]);
}
```