P1853 投资的最大效益

P1853 投资的最大效益

题意：

初始资金为 \(s\) ，一共有 \(n\) 年，\(d\) 种债卷，给出债卷的投资额和年利息，求 \(n\) 年后可以获得的最多资金?

思路:

由于每年之间买债卷是互不影响的，所以我们先看一年如何买。

假设当前资金为 \(sum\) 然后求怎么买收益最高，其实就是一个多重背包问题。每一年做一个多重背包就可以得到答案了。

分析时间复杂度 \(O(n * s * d)\) 是会超时的，所以抓住数据的特点，即债卷的投资额一定是 \(1000\) 的倍数，所以我们每次可以将当前的 \(sum\) 和每个债卷的投资额同时除以 \(1000\) 这样就不会超时了。

实现:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e6 + 5;
ll f[N];
int w[45], v[45];
int main()
{
    int m, n, d;
    scanf("%d%d%d", &m, &n, &d);
    for (int i = 1; i <= d; i++)
        scanf("%d%d", &w[i], &v[i]);

    ll sum = m;
    for (int i = 1; i <= n; i++)
    {
        ll tem = 0;
        for (int j = 0; j < N; j++)
            f[j] = 0;
        for (int h = 1; h <= d; h++)
        {
            for (int j = 1; j <= sum / 1000; j++)
            {
                if (j >= w[h] / 1000)
                {
                    f[j] = max(f[j], f[j - w[h] / 1000] + v[h]);
                }
                tem = max(tem, f[j]);
            }
        }
        sum += tem;
    }
    printf("%lld\n", sum);
    return 0;
}