题解：P17094 [ICPC 2017 Qingdao R] Collecting Cents

· · 题解

题意简述

初始有 n 美分。将 c 美分存 t 年后，可取回 c+\lfloor ct/d\rfloor 美分；所有本金和存期均为整数。可以同时建立多笔存款，并在到期后继续投资。求 y 年后的最大资金。

解题思路

先把每年需要考虑的存款方案缩到常数规模。

同一时间、同一存期的两笔存款合并后不会更差，因为：

\left\lfloor\frac{at}{d}\right\rfloor+\left\lfloor\frac{bt}{d}\right\rfloor \le\left\lfloor\frac{(a+b)t}{d}\right\rfloor

再考虑一笔存期 t\ge2、本金 c\ge d 的存款。从中取出 d 美分，先存一年，再把所得资金存 t-1 年。这部分最终至少得到：

d+1+\left\lfloor\frac{(d+1)(t-1)}{d}\right\rfloor =d+t+\left\lfloor\frac{t-1}{d}\right\rfloor \ge d+t

因此，多年期存款的本金只需考虑 0 到 d-1。

若存期 t>d，令 q=t-d。直接存 t 年得到 2c+\lfloor cq/d\rfloor；先存 d 年得到 2c，再存 q 年至少得到 2c+\lfloor2cq/d\rfloor。后者不小于前者，所以存期也只需考虑到 d。

设当前还剩 m 年，其中 m 在实现中截到 \min(d,m)。枚举 z_t\in[0,d-1]，表示投入 t 年期的本金，其中 2\le t\le m。未分配资金全部存一年，因为保留现金不会增加收益。

先处理单年动作。

设当前现金为 C=qd+r，多年期本金总和为 s。一年期本金为 C-s，下一年由它产生的现金为：

C+q-\left(s-\left\lfloor\frac{r-s}{d}\right\rfloor\right)

括号内只取决于当前余数和动作，代码将其预处理为 cst。若原来还有一年后到期的金额 p_1，再把 p_1 加入即可。

定义多年期存款的到期金额为：

g_t(z)=z+\left\lfloor\frac{zt}{d}\right\rfloor

对固定的 (d,m,r)，将某个动作在未来各年的累计可用增量记为：

\begin{aligned} h_1 & = r-s+\left\lfloor\frac{r-s}{d}\right\rfloor \\ h_k & = h_1+\sum_{t=2}^{k}g_t(z_t) \end{aligned}

若动作 A 使用的多年期本金不多于动作 B，且每个 h_k^A\ge h_k^B，则 A 在每个未来时刻都能提供不少于 B 的累计资金。多余资金可以暂时保留，因此 A 能模拟 B，动作 B 可以删除。

代码不使用递归生成动作，而是把 z_2,z_3,\dots,z_m 看成一个 d 进制数，依次解出每一位。最多只有 d^{d-1}\le7776 个原始动作，并且每个 d 只预处理一次。

再处理跨年份状态。

状态包含当前现金，以及未来 1 到 d-1 年内已经确定的到期金额。每个位置用 6 位打包成一个整数 key。一年转移时，最低 6 位到期并加入现金，其余位右移，新动作产生的 g_t(z_t) 再加到对应位置。

每个到期位置至多合并前 d-1 年建立的存款。每笔返还不超过 2(d-1)，所以单个位置不超过：

2(d-1)^2\le50

生成下一层状态后，先按 key 做基数排序。相同 key 只保留现金最大的状态。

不同 key 之间也存在支配关系。设状态 A 的现金不少于状态 B，差额为 \Delta。让 A 模拟 B 的全部决策，并把多余现金每年存一年。处理下一笔到期金额前，差额的保守下界更新为：

\Delta\leftarrow\Delta+\left\lfloor\frac{\Delta}{d}\right\rfloor+p_i^A-p_i^B

若逐年更新时差额从未变成负数，则 A 始终能够补足 B 的资金，状态 B 可以删除。

这种支配还给出现金值域上界。两个保留状态的现金差小于较差状态全部待到期金额之和，即小于 250。转移中的一年期增长、动作代价和首笔到期金额至多把候选现金值域扩大到 455，所以可以使用计数排序按现金递减处理。

设动作剪枝后每类至多保留 C 个动作，每层保留 P 个状态，按 key 去重后有 K 个候选。每年生成和基数排序需要 O(PC)，状态支配检查需要 O(KPd)。本题 d\le6，这些集合经过两层支配剪枝后都很小。

正确性证明

合并同存期存款、从多年期存款中拆出 d 美分，以及把超过 d 年的存款分段，都不会减少最终资金。因此至少存在一个最优策略，使每笔多年期本金小于 d、存期不超过 d，每年的其余现金全部存一年。动作枚举覆盖了所有这样的策略。

动作剪枝中，支配动作使用的本金更少，并且截至每个未来时刻累计到账金额更多。它可以先保留多余资金，再完全复制被删动作之后的决策，所以删除被支配动作不会删去所有最优策略。

状态去重只在待到期序列完全相同时保留更多现金的状态，因此不会损失更优解。跨状态支配使用的差额递推是实际差额的下界；若下界始终非负，支配状态便能逐年补足另一状态的全部到期收入并复制其决策。因此状态剪枝同样安全。

从初始状态开始按年份归纳，每层转移都枚举了某个最优策略的下一步，随后两种剪枝仍保留一个不劣状态。第 y 年结束时不存在更晚到期的有效存款，保留状态中的最大现金就是答案。

参考代码

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

using ull=unsigned long long;
const int D=7;
const int B=6;
const ull base=1ULL<<B;
struct choice
{
    ull key;
    int sum,cst;
};
struct state
{
    ull key,csh;
};
struct full
{
    ull key;
    int sum,cst;
    int pre[D];
};
int d,y;
bool vis[D];
vector<choice> ch[D][D][D];
vector<state> f,nxt,st,buf,cv,tmp;
int floor_div(int x)
{
    return x>=0?x/d:-(-x+d-1)/d;
}
bool cover(const full &a,const full &b)
{
    if(a.sum>b.sum)return 0;
    for(int i=0;i<d;i++)if(a.pre[i]<b.pre[i])return 0;
    return 1;
}
void init()
{
    if(vis[d])return;
    vis[d]=1;
    for(int i=1;i<=d;i++)
    {
        int m=i;
        int lim=1;
        for(int j=2;j<=m;j++)lim*=d;
        for(int j=0;j<d;j++)
        {
            int r=j;
            vector<full> all,kp;
            for(int k=0;k<lim;k++)
            {
                int cur=k,sum=0;
                int z[D]={};
                int p=2;
                while(p<=m)
                {
                    z[p]=cur%d;
                    cur/=d;
                    sum+=z[p];
                    p++;
                }
                int val=r-sum+floor_div(r-sum);
                full x={0,sum,r-val,{}};
                x.pre[0]=val;
                p=2;
                while(p<=d)
                {
                    int q=p<=m?z[p]+z[p]*p/d:0;
                    x.key|=ull(q)<<(B*(p-2));
                    val+=q;
                    x.pre[p-1]=val;
                    p++;
                }
                all.push_back(x);
            }
            for(auto &x:all)
            {
                bool bad=0;
                for(auto &q:kp)if(cover(q,x)){bad=1;break;}
                if(bad)continue;
                kp.erase(remove_if(kp.begin(),kp.end(),[&](const full &q){return cover(x,q);}),kp.end());
                kp.push_back(x);
            }
            for(auto &x:kp)ch[d][m][r].push_back({x.key,x.sum,x.cst});
        }
    }
}
void radix_sort()
{
    int k=(B*(d-1)+9)/10,siz=cv.size();
    tmp.resize(siz);
    int cnt[1024];
    for(int i=0;i<k;i++)
    {
        memset(cnt,0,sizeof cnt);
        int sh=i*10;
        for(auto &x:cv)cnt[(x.key>>sh)&1023]++;
        for(int j=1;j<1024;j++)cnt[j]+=cnt[j-1];
        for(int j=siz-1;j>=0;j--)tmp[--cnt[(cv[j].key>>sh)&1023]]=cv[j];
        cv.swap(tmp);
    }
}
bool cover(const state &a,const state &b)
{
    ull dif=a.csh-b.csh,x=a.key,y=b.key;
    for(int i=0;i<d-1;i++)
    {
        dif+=dif/d;
        int p=x%base,q=y%base;
        if(p>=q)dif+=p-q;
        else if(dif>=ull(q-p))dif-=q-p;
        else return 0;
        x>>=B;
        y>>=B;
    }
    return 1;
}
void prune()
{
    radix_sort();
    st.clear();
    for(int i=0;i<cv.size();)
    {
        int j=i+1;
        ull csh=cv[i].csh;
        while(j<cv.size()&&cv[j].key==cv[i].key)
        {
            csh=max(csh,cv[j].csh);
            j++;
        }
        st.push_back({cv[i].key,csh});
        i=j;
    }
    ull mx=0,mn=ULLONG_MAX;
    for(auto &x:st)
    {
        mx=max(mx,x.csh);
        mn=min(mn,x.csh);
    }
    vector<int> cnt(mx-mn+1);
    for(auto &x:st)cnt[mx-x.csh]++;
    int sum=0;
    for(auto &x:cnt)
    {
        int val=x;
        x=sum;
        sum+=val;
    }
    buf.resize(st.size());
    for(auto &x:st)buf[cnt[mx-x.csh]++]=x;
    st.swap(buf);
    nxt.clear();
    for(auto &x:st)
    {
        bool bad=0;
        for(auto &q:nxt)if(cover(q,x)){bad=1;break;}
        if(!bad)nxt.push_back(x);
    }
}
ull solve(ull n)
{
    f.clear();
    f.push_back({0,n});
    for(int i=0;i<y;i++)
    {
        cv.clear();
        int m=min(d,y-i);
        for(auto &cur:f)
        {
            ull q=cur.csh/d,bck=cur.key%base;
            int r=cur.csh%d;
            for(auto &x:ch[d][m][r])
            {
                if(cur.csh<ull(x.sum))continue;
                cv.push_back({(cur.key>>B)+x.key,cur.csh+q-x.cst+bck});
            }
        }
        prune();
        f.swap(nxt);
    }
    return f[0].csh;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin>>T;
    while(T--)
    {
        ull n;
        cin>>n>>d>>y;
        init();
        cout<<solve(n)<<'\n';
    }
    return 0;
}