【BUCTOJ】问题H：Harnack函数（动态规划）

样例输入

4 3
           

样例输出

9
           

提示

样例输入2 复制

13 13
           

样例输出2 复制

156
           

这题用动态规划做。

首先审题，发现如果要求H(n,m)，需要从1向上迭代出，符合动态规划题型.dp方程也已经给出,最优子结构为H(n-1,m)+n-1和H(n,m-1)+m-1.那么还剩下枚举确定边界就可以做出该题.

枚举其实也不难。因为我们看到，H(n,m)每次向上迭代都是以H(n或m原数+1,m或n)得出.换言之，从H(n,m)向下迭代是n或m递减的，n或m必有一个数率先达到-1，获取函数的初值。

假设获取初值时函数为H(-1,k)(k>=0),那么向上迭代一次，为H(0,k)=max(H(-1,k)-1,H(0,k-1)+k-1)（1）

如果k=0,前后相等等于0.

如果k>0,那么前者为0，后者需要讨论H(0,k-1)的大小.

对于H(0,k-1)=max(H(-1,k-1)-1,H(0,k-2)+k-2)（2），

假设k=1,那么(2)式前后值相等都等于0，（1）式前后相等都等于0。

假设k=2,那么(2)式需要继续讨论H(0,k-2)的大小，最后回带到(1)式，后者更大等于1。

…

假设k无限大，那么(2)式需要不断向下迭代，发现k必须减至0才能终止迭代.

通过以上操作，我们可以得出推论:初始值必须从H(0,-1)或H(-1,0)开始取，而这个值就是0.同样，H(0,0)=0.

下边界和上边界此时都已确定。

但别着急整dp！再看看这道题，还有更快的解法。

猜想:H(n,m)=((n - 1) * n + (m - 1) * m) / 2;

猜想是最快的解法…但是如果你数学很好，也可以短时间证明一下（我就要用长一点的时间了╮(╯▽╰)╭）：

讨论H(1,m),H(2,m),…,H(n,m)。

对于H(1,m)=max(H(0,m)+0,H(1,m-1)+m-1),

对于H(0,m),从(0,-1)向上迭代知H(0,m)=m*(m-1)/2;

由上述迭代方法知讨论H(1,m-1)的大小需要向下迭代。

此处不一一解，给出H(1,m-1)=m-2+m-1;

讨论m*(m-1)/2与2m-3的大小关系：

联立m*(m-1)/2与2m-3的不等式，假设前者大于后者；

得出m^2-5m+6>0

当2<m<3时，前者小于后者.

当m<=2或m>=3时，前者大于等于后者。

m只有整数解。换言之，在整数区间内H(0,m)+0>=H(1,m-1)+m-1;

这也就是说H(1,m)会取到H(0,m).

你可以继续如此讨论H(2,m).会发现依然如此，取到的还是H(1,m)+1;如此向上迭代，自然发现迭代了n次，从0加到了n-1.根据等差数列和，易得H(n,m)=((n - 1) * n + (m - 1) * m) / 2.

给出代码，1ms（虽然但是都说到这儿了还有给的必要么）:

#include<iostream>
#include<cstring>
#include<cstdio>
#include<string>
#include<cmath>
#include<vector>
#include<set>
#include<algorithm>

typedef long long ll;
//dp
using namespace std;

int main()
{
    int n, m;
    cin >> n >> m;
    int s;
    s = ((n - 1) * n + (m - 1) * m) / 2;
    if (n >= 0 && m >= 0)
        cout << s << endl;
    else
        cout << 1 << endl;

    return 0;
}