题意分析

题目描述了一个封闭式基金（Closed-End Fund）的投资管理场景，其中基金经理 Frank 在固定期限内（m 天）管理基金，通过买卖股票最大化最终收益。基金初始现金为 c（单位：USD），Frank 可以投资于 n 只股票。关键约束包括：

• 每日操作限制：每天只能执行一笔交易（BUY、SELL 或 HOLD），且买卖操作以“整手”为单位（每手股数 s_i 由股票决定），不能部分交易。
• 持股上限：每只股票最多持有 k_i 手（local limit），且总持股手数不能超过 k（global limit）。
• 价格数据：每只股票每天的价格已知，Frank 可以在任何一天买入或卖出，但交易基于当天的固定价格（忽略手续费）。
• 结束条件：基金结束时（m 天后），所有股票必须卖出，现金按比例分配给投资者。

问题目标：给定所有股票的价格序列，计算 Frank 能实现的最大收益（即最终现金），并输出每天的操作序列（BUY、SELL 或 HOLD）以达成该收益。

解题思路

解题需解决两个部分：(1) 计算最大收益值；(2) 构造操作序列。由于问题规模较小（n ≤ 8, k ≤ 8, m ≤ 100），状态压缩动态规划（DP） 是高效解法。思路基于枚举所有可能的持股状态，并使用 DP 状态转移模拟每日决策。以下是详细步骤：

1. 预处理：建模与状态定义

• 状态表示：持股状态可编码为一个整数（hash），表示每只股票的当前持股手数。每只股票 i 的持股数 h_i 范围是 0 到 k_i（由于 k_i ≤ k ≤ 8, 取值不超过 9），因此状态可用 n 位 base-9 数字表示：
  • 总状态数上限：(k+1)^n ≈ 9^8 = 43,046,721，但实际合法状态更少（需满足总手数 ∑h_i ≤ k）。
  • 代码实现时（参考题解代码），使用数组 num[] 存储所有合法状态（通过 DFS 生成），并用 match[] 映射状态到索引，加速查找。
• DP 状态定义：
  • dp[day][state]：表示第 day 天结束时（持股状态为 state）的最大现金值。
  • 初始化：dp[0][0] = c（第 0 天结束，无持股，现金为初始值），其他状态设为无效值（如 -1）。
  • 最终目标：dp[m][0]（第 m 天结束，所有股票卖出，持股状态为 0），存储最大现金。
• 决策记录：辅助数组 rem[day][state] 存储转移路径（操作类型和股票索引），用于后续生成操作序列。

2. DP 状态转移（核心算法）

对于每一天 day（从 1 到 m），遍历所有状态 state，计算三个可能操作：

• HOLD（不操作）：
  • 状态不变：new_state = state。
  • 转移：dp[day][new_state] = max(dp[day][new_state], dp[day-1][state])。
  • 决策记录：标记为 HOLD。
• BUY 股票 i（买入一手）：
  • 条件：当前现金 dp[day-1][state] ≥ price[i][day] * s_i（足够买入），且买入后 h_i < k_i 且总手数 ∑h_i ≤ k - 1。
  • 状态更新：new_state = state + pow9[i]（base-9 表示，pow9[i] 是 i 位置的权重）。
  • 现金更新：dp[day][new_state] = max(... , dp[day-1][state] - price[i][day] * s_i)。
  • 决策记录：标记 BUY 和股票 i。
• SELL 股票 i（卖出一手）：
  • 条件：当前状态持有股票 i（h_i > 0）。
  • 状态更新：new_state = state - pow9[i]。
  • 现金更新：dp[day][new_state] = max(... , dp[day-1][state] + price[i][day] * s_i)。
  • 决策记录：标记 SELL 和股票 i。
• 转移优化：使用滚动数组（如 dp[0][] 和 dp[1][] 交替）减少内存使用，因为 m 较小但状态数多。

3. 生成操作序列

• 回溯法：从最终状态 dp[m][0] 开始，反向遍历每一天，根据 rem[day][state] 记录的决策：
  • 如果 rem[day][state] 是 HOLD，则操作序列添加 HOLD。
  • 如果 BUY 或 SELL，添加对应操作（如 BUY GOOG），并更新状态（移除或添加影响）。
  • 回溯到前一天状态，重复直到 day 0。
• 输出序列：操作序列与天数顺序一致（第 1 天到第 m 天）。

4. 复杂度与优化

• 时间复杂度：O(m * |S| * n)，其中 |S| 是状态数（约 O((k+1)^n)）。由于 n ≤ 8, k ≤ 8，状态数约 4.3e7，但在代码中通过预处理只枚举合法状态（如示例代码的 num[0] 表示总状态数），实际运行可行。
• 空间复杂度：O(|S| * m)，但通过滚动数组优化为 O(|S|)。
• 数值处理：为避免浮点误差，现金和价格乘以 100 转为整数（单位：分），计算后再恢复。
• 实际参考：题解代码（C++）直接实现了上述逻辑，使用 rem[] 记录操作，并通过 DFS 生成状态。

示例代码

#include<cstdio>
#include<cstring>
#include<map>
#include<algorithm>
using namespace std;
short rem[101][130100][2];
int n,m,pow9[10],ki[10],K,num[13010],num2[13010],num3[13010][10],match[50000000];
double dp[2][130100],val[10][110];
char s[10][20];
void pai(int pos,int u,int Hash)
{
    int i;
    if(pos==m+1)
    {
        num[0]++;
        num[num[0]]=Hash;
        num2[num[0]]=u;
        match[Hash]=num[0];
        for(i=1;i<=m;i++)
        {
            num3[num[0]][i]=Hash%9;
            Hash/=9;
        }
        return;
    }
    for(i=0;i<=ki[pos];i++)
       if(u+i<=K)
           pai(pos+1,u+i,Hash+i*pow9[pos]);
       else
         return;
}
void mem(int a)
{
    for(int i=1;i<=num[0];i++)
       dp[a][i]=-1;
}
void print(int day,int Hash)
{
    if(day==0)
      return;
    int Hash2=Hash,now=match[Hash];
    if(rem[day][now][0]==-1)
      Hash2+=pow9[rem[day][now][1]];
    else if(rem[day][now][0]==1)
      Hash2-=pow9[rem[day][now][1]];
    print(day-1,Hash2);
    if(rem[day][now][0]==0)
    {
        printf("HOLD\n");
    }
    else
    {
        if(rem[day][now][0]==-1)
          printf("SELL ");
        else
          printf("BUY ");
        printf("%s\n",s[rem[day][now][1]]);
    }
}
int main()
{
    int i,j,k,k2,ret,a,b,now,to;
    double c;
    pow9[1]=1;
    for(i=2;i<=9;i++)
       pow9[i]=pow9[i-1]*9;
    while(~scanf("%lf%d%d%d",&c,&n,&m,&K))
    {
        for(i=1;i<=m;i++)
        {
            scanf("%s%d%d",s[i],&ret,&ki[i]);
            for(j=1;j<=n;j++)
            {
                scanf("%lf",&val[i][j]);
                val[i][j]*=ret;
            }
        }
        num[0]=0;
        pai(1,0,0);
        mem(0);
        dp[0][1]=c;
        for(i=1;i<=n;i++)
        {
            if(i&1)
              a=0,b=1;
            else
              a=1,b=0;
            mem(b);
            for(j=1;j<=num[0];j++)
            if(dp[a][j]>=0)
            {
                now=j;
                if(dp[a][now]>dp[b][now])
                {
                    dp[b][now]=dp[a][now];
                    rem[i][now][0]=0;
                }
                for(k=1;k<=m;k++)
                {
                    k2=num3[j][k];
                    if(k2>0)
                    {
                        to=match[num[j]-pow9[k]];
                        if(dp[b][to]<dp[a][now]+val[k][i])
                        {
                            dp[b][to]=dp[a][now]+val[k][i];
                            rem[i][to][0]=-1;
                            rem[i][to][1]=k;
                        }
                    }
                    if(k2<ki[k] && num2[j]<K && dp[a][now]>=val[k][i])
                    {
                        to=match[num[j]+pow9[k]];
                        if(dp[b][to]<dp[a][now]-val[k][i])
                        {
                            dp[b][to]=dp[a][now]-val[k][i];
                            rem[i][to][0]=1;
                            rem[i][to][1]=k;
                        }
                    }
                }
            }
        }
        printf("%.2f\n",dp[b][1]);
        print(n,0);
    }
}