[Solution][Dynamic Programming][四边形不等式]JDFZOJ2439 合并沙子

【题目】

戳这里

【思路】

题意有点梗的经典动态规划(2D/1D)模型。

也就是状态量是,决策转移是的动态规划。

总共的时间复杂度为.

一般的,我们可以把这种经典模型优化到,即实现转移。

引入四边形不等式的优化。

设一种决策函数.

其中可以通过计算。

区间包含性:

四边形不等式:

可以证明,如果满足四边形不等式以及区间包含性,亦满足这些性质。

我们记转移的当前最优决策,则可以证明

我们的优化就从这里开始。

只需记录上层阶段的最优决策,枚举当前状态决策时在如上的区间枚举。于是转移的时间复杂度变为.

总时间复杂度为.

(PS:当然不排除有更加优秀的算法,对于这个问题某些算法能够利用“二递减性”做到,不过目前没有兴趣。)

【代码】

#include<cstdio>
#include<cstring>
#define get(x  , y) add[y] - add[x - 1]
#define clear(x , y) memset(x , y , sizeof(x))
inline int _min(int a , int b)
{
    return a < b ? a : b;
}
const int N = 1010;
int A[N] , add[N] , dp[N][N] , g[N][N];
int main()
{
    int n;
    scanf("%d" , &n);
    register int i , j , k;
    for(i = 1 ; i <= n ; ++i)
    {
        scanf("%d" , &A[i]);
        add[i] = add[i - 1] + A[i];
    }
    clear(dp , 0x3f);
    for(i = 1 ; i <= n ; ++i)
    {
        dp[i][i] = 0;
        g[i][i] = i;
    }
    for(k = 2 ; k <= n ; ++k)
    for(i = 1 ; i + k - 1 <= n ; ++i)
    {
        for(j = g[i][i + k - 2] ; j <= g[i + 1][i + k - 1] ; ++j)
            if (dp[i][i + k - 1] > dp[i][j] + dp[j + 1][i + k - 1] + get(i , i + k - 1))
            {
                dp[i][i + k - 1] = dp[i][j] + dp[j + 1][i + k - 1] + get(i , i + k - 1);
                g[i][i + k - 1] = j;
            }
    }
    printf("%d" , dp[1][n]);
    return 0;
}
comments powered by Disqus