前言:
其实写这个博客的原因是在康其他人的windy数代码的时候,发现有的人的结果输出是work(b+1)-work(a),有的人的结果输出是work(b)-work(a-1),很奇怪为什么是这样的,所以就有了这篇博客
正文:
对于work(b+1)-work(a),其状态设置为dp[i][j]表示处理到第i位数,第i位数之前的值是j
对于work(b)-work(a-1),其状态设置为f[i][j]表示处理到第i位数,第i位数的值是j
很容易发现两个状态的差异,一个处理前面,一个处理后面,而正是因为这个差异,所以导致了结果的差异
对于第一个dp,我们发现如果枚举b-a这个区间,区间里的所有值都是可以被遍历的,所以我们直接按照常规方式输出work(b)-work(a-1)即可
对于第二个f,如果枚举b-a这个区间,最后枚举的只是绿色的两个格子(有界),所以输出结果是work(b+1)-work(a)
就是这样啦~~