常数 dp 学习笔记

· · 题解

2017 年的管理组：

本题的恶搞题解到此为止。

为防止新人受到误导，不再接受新的此类题解。

以前的保留不会删除，但请不要再提交。

2025 年的管理组：

鼓励全新的大炮（核弹）打蚊子技术。

注意到是大炮打蚊子而不是其他什么的，合理推测大炮在本题中有着极其重要的地位。

观察大炮这个词语，注意到其首字母是 dp，而主题库内的算法标签恰好有动态规划 dp，这启示我们利用动态规划通过此题。

于是我们定义 f_{i,j} 为 i+j 的值，答案即为 f_{a,b}。

接下来考虑转移。

注意到 f_{i,j}=f_{i,j-1}+1，于是就可以照着转移了。

时间复杂度 O(n^2)。

但是数据范围太大了！我们需要优化这个柿子。

又注意到 f_{i,j}=f_{i,0}+j，于是这样我们就优化成了 O(n)。

可还是过不了，怎么办？

因为 f_{i,0}>f_{i-1,0}，具有单调性，可以使用二分来优化 dp。

考虑二分 i 的值，找到后进行转移。

可是数组开不下，而且有负数呢！

我有一计，线性 dp 有点难做，那我们原创一种常数 dp 吧！

由于我贿赂了管理员窃取了数据进行了打表，得到结论 f_{i,0}=i，虽然我不会证，但是，很神奇吧！

管理员会不会要我补充对于重要结论的证明呢。

那么还是证明一下的好：

首先 f_{i,j}=i+j。

因为 j=0，于是 f_{i,0}=i+0=i。

所以 f_{i,0}=i！

那么我们只需要初始化一下，然后进行转移就可以了！

这个时候有人要问了，主播主播那你怎么开数组呢？

答案是红黑树！实现的 map。

于是我们就写完啦！

#include<bits/stdc++.h>
using namespace std;
map<pair<int,int>,int>mp;
int main(){
    int a,b;
    cin>>a>>b;
    mp[make_pair(a,0)]=a;
    mp[make_pair(a,b)]=mp[make_pair(a,0)]+b;
    cout<<mp[make_pair(a,b)];
    return 0;
}

总结，这是一道非常棒的常数 dp 练手题。

但是这个算法不在 CCF 的考纲上，应该是 CCF 太弱了还不会这么高级的算法，对吧。

不考实在太可惜了。

怎么评论区都在问证明这句话的意思：

所以 f_{i,0}=i！

所以解释一下吧。

观察式子，注意到是中文感叹号，这启示我们并非阶乘。

换 @llamn 言之：

观察题解，注意到原文 $f_{i,0}=i$！ 中感叹号没有在 \LaTeX 公式中，启示我们感叹号的含义并非阶乘。

观察。注意。启示。