常数 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。

于是我们就写完啦！

CPP

#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

公式中，启示我们感叹号的含义并非阶乘。

观察。注意。启示。

文章操作

相关推荐

评论

常数 dp 学习笔记