【2024信友队 - 提高模考】 新编套题2 T3：幸苦的工作

题面 ：幸苦的工作（Work.cpp）

题目描述

​ 在工作中，小明有 $n$ 个任务要完成。第个任务有一个基础时间t和额外时间 $p_i$。（ $t$ 是互不相同的，$p_i$ 也是互不相同的）
​ 如果在做任务之前小明已经做了 $k$ 个任务，则做这个任务需要 $t+k·p$ 的时间（因为任务繁重，小明累了）现在小明还剩下的时间为 $T$ ，请问他在这段时间内最多能做多少个任务（假定任务之间没有依赖关系）。（题目保证 $t,p$ 不重）

思路：暴搜 & DP (劣) & DP (std)

首先的，暴力枚举每个工作的顺序，求答案。代码略（伪代码也别想要）

然后我们开始考虑正解，这道题，一眼丁真就是 DP 。关键在于怎么 DP 。突然发现有点像背包，而且 $t$ 和 $p$ 不重发现完全是可以在 1000 以内完成，给人物按照 $p$ 排序，跑背包即可。

代码：正解代码

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
typedef long long ll;

int n, T;
struct Node {
    ll t, p;
    friend bool operator <(Node &a, Node& b) {
        return a.p > b.p;
    }
}a[N];

ll dp[N];

void Input() {
    scanf("%d%d", &n, &T);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i].t);
    }
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i].p);
    }
}

void Work() {
    sort(a + 1, a + n + 1);
    memset(dp, 0x3f, sizeof dp);
    dp[0] = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1000; j >= 1; j--) {
            dp[j] = min(dp[j], dp[j - 1] + a[i].t + a[i].p * (j - 1));
        }
    }
    for (int i = n; i >= 0; i--) {
        if (dp[i] <= T) {
            printf("%d", i);
            break;
        }
    }
}

int main() {
    Input();
    Work();
    return 0;
}