【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;
}