1137. 河床

TAG 动态规划

地理学家们经常要对一段河流进行测量分析。他们从上游开始向下游方向等距离地选择了 n( ≤ 30000) 个点测量水位深度。得到一组数据 d1 ， d2 ，……， dn ， 回到实验室后数据分析员根据需要对数据进行分析，发掘隐藏在数据背后的规律。最近，乌龙博士发现某种水文现象与河床地势有关，于是他指示他手下的分析员要 找出一段河流中最大高低起伏差不超过 k( ≤ 100) 的最长一段。这看似一个复杂的问题，由于任务紧急，分析员来 求助于你，并告诉你博士的所有数据都精确到个位。

设 dp[n][k] 为在第n个测量点，在满足接下来水位能下降k的前提下，之前连续的的一段最多有多长。

令 down= depth[i-1]-depth[i]+j；

则 dp[i][j]= 1 if down<0 或者 down>k

dp[i-1][k]+1 if down>=0 且 down<=k

空间方面可以用滚动数组优化，因为求dp[i]只需dp[i-1]，不需要之前其他数据。

时间复杂度是O(nk),暴搜时间复杂度是O(n^2),因为暴搜时，水深不满足便停止，绝大部分情况下长度<k，结果暴搜反而比动态规划速度要快。

囧 (‖▔ ω▔)我花了好多时间才想出怎么dp的。。。

0.08s 12212KB //dp
0.04s 376KB //暴搜

dp的代码：

/* source code of submission 428081, Zhongshan University Online Judge System */
#include <stdio.h>
const  int N=30000;
int ans;
int n,k;
int depth[N];
int dp[N][101];
int main(int argc, char *argv[])
{
    scanf("%d%d", &n, &k);
    for (int i=0; i<n; ++i)
    {
        scanf("%d", &depth[i]);
    }

    for (int i=0; i<=k; ++i)
    {
        dp[0][i]=1;
    }
    ans=1;
    for (int i=1; i<n; ++i)
    {
        for (int j=0; j<=k; ++j)
        {
            int down=depth[i-1]-depth[i];
            down=j+down;
            if ( down>=0 && down<=k)
            {
                dp[i][j]=dp[i-1][down]+1;
            }
            else
            {
                dp[i][j]=1;
            }
            if ( dp[i][j]>ans )
            {
                ans=dp[i][j];
            }
        }
        
    }
    printf("%d/n", ans);
    return 0;
}