P1853 投资的最大效益

题目背景

约翰先生获得了一大笔遗产，他暂时还用不上这一笔钱，他决定进行投资以获得更大的效益。银行工作人员向他提供了多种债券，每一种债券都能在固定的投资后，提供稳定的年利息。当然，每一种债券的投资额是不同的，一般来说，投资越大，收益也越大，而且，每一年还可以根据资金总额的增加，更换收益更大的债券。

题目描述

例如：有如下两种不同的债券：

1. 投资额 $\mathrm{\$}4000$，年利息 $\mathrm{\$}400$；
2. 投资额 $\mathrm{\$}3000$，年利息 $\mathrm{\$}250$。

初始时，有 $\mathrm{\$}10000$ 的总资产，可以投资两份债券 1 债券，一年获得 $\mathrm{\$}800$ 的利息；而投资一份债券 1 和两份债券 2，一年可获得 $\mathrm{\$}900$ 的利息，两年后，可获得 $\mathrm{\$}1800$ 的利息；而所有的资产达到 $\mathrm{\$}11800$，然后将卖掉一份债券 2，换购债券 1，年利息可达到 $\mathrm{\$}1050$；第三年后，总资产达到 $\mathrm{\$}12850$，可以购买三份债券 1，年利息可达到 $\mathrm{\$}1200$，第四年后，总资产可达到 $\mathrm{\$}14050$。

现给定若干种债券、最初的总资产，帮助约翰先生计算，经过 $n$ 年的投资，总资产的最大值。

输入格式

第一行为三个正整数 $s,n,d$，分别表示最初的总资产、年数和债券的种类。

接下来 $d$ 行，每行表示一种债券，两个正整数 $a,b$ 分别表示债券的投资额和年利息。

输出格式

仅一个整数，表示 $n$ 年后的最大总资产。

说明/提示

对于 $100\mathrm{\%}$ 的数据，$1\le s\le {10}^6$，$2\le n\le 40$，$1\le d\le 10$，$1\le a\le {10}^4$，且 $a$ 是 $1000$ 的倍数，$b$ 不超过 $a$ 的 $10\mathrm{\%}$。

思路

看着像完全背包，因为是原价卖，所以本年能收的最大利息只与本金有关，与之前怎么买的无关，所以按照收益递推就可以了，逐年递推，用dp求收益

顺着思路写出来：

#include <iostream>
#include <cstring>
#define ll long long

using namespace std;

struct
{
    int a;
    int b;
} debt[50];

int dp[50000];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    memset(dp, 0, sizeof(dp));
    int s, n, d;
    cin >> s >> n >> d;
    for (int i = 1; i <= d; i++)
    {
        cin >> debt[i].a >> debt[i].b;
        debt[i].a /= 1000;
    }

    float m = 1.1;
    for (int i = 0; i < n; i++)
    {
        m = m * m;
    }

    int maxj = (s * m) / 1000 + 1;

    for (int i = 1; i <= d; i++)
    {
        for (int j = debt[i].a; j <= maxj; j++)
        {
            dp[j] = max(dp[j], dp[j - debt[i].a] + debt[i].b);
        }
    }
    int money = s;
    // 逐年递推
    for (int i = 0; i < n; i++)
    {
        money += dp[money / 1000];
    }
    cout << money;
    return 0;
}

提交，全红 x_x

下载看看测试点: 1000000 40 10 1000 100 1000 100 1000 100 1000 100 1000 100 1000 100 1000 100 1000 100 1000 100 1000 100 居然1000000原样输出了,查一下bug

发现下面这种情况会出现inf:

    double m = 1.1;
    for (int i = 0; i < 40; i++)
    {
        m = m * m;
    }
    cout << m;

粗心了,这里应该是m *= 1.1

改了之后依然全红,第一个测试点输出值只有答案的一半,失手把年份改了,改完应该可以了

ac!

题解

#include <iostream>
#include <cstring>
#define ll long long
#define debug(x) #x << ":" << x << " "

using namespace std;

struct
{
    ll a;
    ll b;
} debt[50];

ll dp[50000];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    memset(dp, 0, sizeof(dp));
    ll s, n, d;
    cin >> s >> n >> d;
    for (int i = 1; i <= d; i++)
    {
        cin >> debt[i].a >> debt[i].b;
        debt[i].a /= 1000;
    }

    double m = 1.1;
    for (int i = 0; i < n; i++)
    {
        m *= 1.1;
    }
    // cout << debug(s) << debug(m) ;
    ll maxj = (s * m) / 1000 + 1;
    // cout << maxj << " ";
    // cout << debug(maxj);

    for (int i = 1; i <= d; i++)
    {
        for (int j = debt[i].a; j <= maxj; j++)
        {
            dp[j] = max(dp[j], dp[j - debt[i].a] + debt[i].b);
        }
    }
    ll money = s;
    // 逐年递推
    for (int i = 0; i < n; i++)
    {
        // cout << debug(money);
        money += dp[money / 1000];
    }
    cout << money;
    return 0;
}