本文共 1611 字，大约阅读时间需要 5 分钟。

1. 题目

Twitter正在测试一种名为Pigeon的新工作处理服务。

Pigeon可以用任务实际持续时间的两倍处理任务，并且每个任务都有一个权重。

给定Pigon服务的最大运行时间，任务的实际运行时间和权重，确定Pigon服务在一小时内可以实现的最大总权重。

输入包括以下参数：

n : 任务数量weights : 每个任务的权重tasks : 每个任务实际持续时间p : Pigeon一小时的最大运行时间

示例样例1输入:4[2,4,4,5][2,2,3,4]15输出: 10说明:你可以运行0、1、2号任务，将花费2 * (2 + 2 + 3) = 14 分钟并获得 2 + 4 + 4 = 10 权重。样例2输入:3[3,2,2][3,2,2]9输出: 4说明:你可以运行1、2号任务，将花费2 * (2 + 2) = 8 分钟并获得 2 + 2 = 4 权重。

2. 解题

class Solution {
   public:    /**     * @param n: the number of tasks     * @param weights: the weight for every task     * @param tasks: the actual duration of every task     * @param p: maximum runtime for Pigeon in an hour     * @return: the maximum total weight that the Pigeon service can achieve in an hour     */    int maxWeight(int n, vector
   
     &weights, vector
    
      &tasks, int p) {
           // write your code here        vector
     
      
       > dp(n, vector
       
        (p+1, -1));        // dp[i][j] 表示处理完 i 任务，花费时间为 j 时 的最大权重和        dp[0][0] = 0;        if(tasks[0]*2 <= p)            dp[0][tasks[0]*2] = weights[0];        for(int i = 1; i < n; i++)        {
               dp[i] = dp[i-1];//复制上一次的状态，当前的任务不做            for(int t1 = 0; t1 < p; t1++)            {
                   if(dp[i-1][t1] != -1 && t1+2*tasks[i] <= p)                {
   	//当前任务做                    dp[i][t1+2*tasks[i]] = max(dp[i][t1+2*tasks[i]], dp[i-1][t1]+weights[i]);                }            }        }        return *max_element(dp[n-1].begin(), dp[n-1].end());    }};
       
      
     
    
   

53ms C++

第4题：

我的CSDN

长按或扫码关注我的公众号（Michael阿明），一起加油、一起学习进步！

转载地址：https://michael.blog.csdn.net/article/details/111402361 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！