题解 | #codeforces#

codeforces

https://ac.nowcoder.com/acm/problem/21314

首先看完题目想到了《挑战程序设计竞赛》书里的01背包问题： alt alt 但这里有点不同，每个元素（这里就是每道题）的得分会随着时间减少，意味着我们不仅要像01背包中一样考虑好每个元素的选取与否，还要考虑选取元素的顺序！

所以就有两个部分，一个部分确定元素的顺序，一个部分确定那些元素可以选取

首先是元素顺序的确定。有如下例子：假定有两个元素 q1, q2 其三个属性（得分，每秒得分损失，解题所需时间）分别为 q1.point,q1.loss,q1.need q2.point,q2.loss,q2.need,

衡量谁前谁后的肯定是总的得分

那么q1在前总得分为 q1.point+q2.point-(q1.need*q1.loss+(q2.need+q1.need)*q2.loss)

而q2在前的总得分为 q1.point+q2.point-(q2.need*q2.loss+(q2.need+q1.need)*q1.loss)

所以如果q1在前那么就有q1.need*q1.loss+q2.need*q2.loss+q1.need*q2.loss<q2.need*q2.loss+q2.need*q1.loss+q1.need*q1.loss

继续化简：q1.need*q1.loss+q2.need*q2.loss+q1.need*q2.loss<q2.need*q2.loss+q2.need*q1.loss+q1.need*q1.loss q1.need*q1.loss+q1.need*q2.loss<q2.need*q1.loss+q1.need*q1.loss

(q1.need-q2.need)*q1.loss<(q1.loss-q2.loss)*q1.need

q1.need*q1.loss-q2.need*q1.loss<q1.loss*q1.need-q2.loss*q1.need

-q2.need*q1.loss<-q2.loss*q1.need

q2.loss*q1.need<q2.need*q1.loss
其次是元素选取的确定。思路就类似于01背包问题，dp[j]表示前j分钟可以得到的“最大”得分,对于每次每个题i的判断，有是否完成该题两种情况，完成那么就是dp[j-need]+point-loss*j;不完成就是d[j];最后取dp[全部限制时间]即可；

但是这样的结果并不正确，比如下面这个例子：只有一个题目其point是700，loss是10，need是20，限制时间是60。

显然由于题目只有一个选项，肯定是要做，那么结果即为dp[60]，而dp[60]=max(dp[60-20]+700-1060,dp[60]); 即为0+700-600=100，但是如果一开始就做这道题结果应该为700-1020=500,所以上述思路有问题，原因还是每道题目的分值会随时间衰减。每次应该取的不是dp[全部限制时间]，而是dpmax;

#include<bits/stdc++.h>
using namespace std;
struct que{
     long long point;
     long long loss;
     long long need;
     friend bool operator <(struct que q1,struct que q2){
         return q1.loss*q2.need>q2.loss*q1.need;
     }
}test[100000+5];
long long dp[100000+5];

int main(void)
{
    int t,n;
    cin>>t>>n;
    for(int i=1;i<=t;i++)
    {
        cin>>test[i].point;
    }
    for(int i=1;i<=t;i++)
    {
        cin>>test[i].loss;
    }
    for(int i=1;i<=t;i++)
    {
        cin>>test[i].need;
    }
    dp[0]=0;
    sort(test+1,test+t+1);
    for(int i=1;i<=t;i++)
    {
       for(int j=n;j>=test[i].need;j--)
       {
           dp[j]=(dp[j-test[i].need]+test[i].point-test[i].loss*j)>dp[j]?(dp[j-test[i].need]+test[i].point-test[i].loss*j):dp[j];
       }
    }
    long long max=0;
    for(int i=1;i<=n;i++)
        max=max>dp[i]?max:dp[i];
    cout<<max;
    return 0;
}