问题分析

题目要求计算在给定初始本金、投资年限和若干债券的面值及利息的情况下，通过最优的债券购买和调整策略，使得投资期结束后的资金总额最大化。问题的核心在于如何在每年动态调整债券组合以最大化利息收益。

解题思路

1. 动态规划的应用

   • 由于每年的本金会根据上一年的利息收益增加，因此需要逐年动态调整债券组合。
   • 每年可以将问题视为一个01背包问题：在当前本金的限制下，选择若干债券以最大化利息收益。
   • 动态规划的状态定义为 f[j]，表示在当前本金限制下，能够获得的最大利息收益。

2. 债券面值和利息的处理

   • 债券的面值和利息均以1,000美元为单位，因此可以将所有金额除以1,000，简化计算。

3. 逐年更新本金

   • 每年根据上一年的最优利息收益更新本金：tot += f[tot/1000]。

4. 最终输出

   • 经过所有年份的动态调整后，输出最终的本金总额。

代码解析

以下是代码的详细解析：

#include<iostream>
#include<queue>
#include<stack>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include<set>
#include<string>
#define MP make_pair
#define SQ(x) ((x)*(x))
typedef int int64;
const double PI = acos(-1.0);
const int INF = 0x3f3f3f3f;
using namespace std;

const int MOD = 1000000007;
const int MAXN = 13; // 最多10种债券
const int ADD = 1000*100; // 用于简化计算

int tot, y, n; // 初始本金、投资年数、债券种类数
int c[MAXN], w[MAXN]; // 债券面值和年利息
int f[100030]; // 动态规划数组，用于存储最大利息收益

int main(){
    int nCase;
    scanf("%d", &nCase); // 测试用例数量
    while(nCase--){
        scanf("%d%d%d", &tot, &y, &n); // 输入初始本金、投资年数和债券种类
        for(int i=0; i<n; ++i){
            scanf("%d%d", &c[i], &w[i]); // 输入每种债券的面值和年利息
            c[i] /= 1000; // 将面值除以1000简化计算
        }

        for(int i=0; i<y; ++i){ // 每年进行一次动态规划
            for(int j=0; j<=tot/1000; ++j) // 初始化动态规划数组
                f[j] = 0;
            for(int j=0; j<n; ++j){ // 遍历每种债券
                for(int v=c[j]; v<=tot/1000; ++v) // 从债券面值开始到当前本金
                    f[v] = max(f[v], f[v-c[j]]+w[j]); // 更新最大利息收益
            }
            tot += f[tot/1000]; // 更新本金
        }
        printf("%d\n", tot); // 输出最终本金
    }
    return 0;
}

关键点解释

1. 债券面值和利息的简化

   • 债券的面值和利息均以1,000美元为单位，因此代码中将所有金额除以1,000，减少计算量。

2. 动态规划数组 f[j] 的定义

   • f[j] 表示在当前本金限制下，能够获得的最大利息收益。例如，f[10] 表示在本金为10,000美元时的最大利息收益。

3. 01背包问题的实现

   • 内层循环 for(int v=c[j]; v<=tot/1000; ++v) 是典型的01背包问题的实现方式，通过动态规划更新最大利息收益。

4. 逐年更新本金

   • 每年根据上一年的最大利息收益更新本金：tot += f[tot/1000]。

复杂度分析

• 时间复杂度
  • 每年需要对每种债券进行动态规划，时间复杂度为 (O(y \times \frac{tot}{1000} \times n))，其中 (y) 是投资年数，(\frac{tot}{1000}) 是最大本金单位数，(n) 是债券种类数。
• 空间复杂度
  • 主要用于存储动态规划数组 f，空间复杂度为 (O(\frac{tot}{1000}))。

总结

本题通过动态规划解决了每年动态调整债券组合以最大化利息收益的问题。代码实现清晰，利用01背包问题的思路，逐年更新本金，最终得到最优的总投资收益。