NOIp提高组 2013 花匠

果然,直接DP不做特殊条件判定时,数据规模到一定程度时,必定超时了

看了lei(机房某大佬)的代码,if(dp[i][0]!=1&&dp[i][1]!=1) break; 依然不知是何居心,猜测可能是满足m>1不能同时满足那个条件吧.想不出

接着进一步分析:

受到以前有个题求序列连续和的启发,我们可以这样设计状态:

令f[i][0]表示前i株花中的最后一株(不一定是i)满足条件A时的最多剩下的株数,

f[i][1]表示前i株花作为序列终点且最后一株(不一定是i)满足条件B时的最多剩下的株数,可以得到:

h[i]>h[i-1]时,

f[i][0]=max{f[i-1][0],f[i-1][1]+1}, f[i][1]=f[i-1][1];

h[i]==h[i-1]时,

f[i][0]=f[i-1][0],f[i][1]=f[i-1][1];

h[i]<h[i-1]时,

f[i][0]=f[i-1][0],f[i][1]=max{f[i-1][1],f[i-1][0]+1}.

答案ans=max{f[n][0],f[n][1]};

边界为f[1][0]=f[1][1]=1。

这样算法的时间复杂度可以降到O(n),很快就可以通过。

合理设计状态能够更好地发挥动态规划的优势

上代码:

#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 100010;
int h[maxn], n;
int f[maxn][2];
void init()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i) scanf("%d", &h[i]);
}
void work()
{
    f[1][0] = f[1][1] = 1;     //初始化
    for(int i=2; i <=n; ++i)   //依次递推分析,波动DP,看第i株花怎么放进波动序列
    {
        if(h[i-1] < h[i])      //最后一个比上一个大的情况时,更新条件A,判断条件B的f[i-1][1]+1
        {
            f[i][0] = max(f[i-1][0], f[i-1][1] + 1);
            f[i][1] = f[i-1][1];
        }
        else if(h[i-1] > h[i]) //最后一个比上一个小的情况时,,更新条件B,判断条件A的f[i-1][0]+1
        {
            f[i][1] = max(f[i-1][1], f[i-1][0] + 1);
            f[i][0] = f[i-1][0];
        }
        else                   //h[i-1]==h[i],相等的情况下,无任何处理
        {
            f[i][1] = f[i-1][1];
            f[i][0] = f[i-1][0];
        }
    }
    printf("%d", max(f[n][0], f[n][1]));
}
int main()
{
    init();
    work();
    return 0;
}

在前面使用动态规划的方法,并优化DP的过程之后,解决了问题。

回过头想想,其实问题可以更简化,思维也能更简单清晰。

那么问题转化为:要怎么才能得到一个最长的波动锯齿形的序列了?

观察 5 4 3 2 1 2 事实上可以转化为 5 1 2 ,或 2 1 2 等,即5 4 3 2多个连续递减的点可以使用一个点替代,

其中1是一个转折点,(事实上序列为了实现锯齿形波动效果,多个连续的点都可以用一个点替代)

那么上面的问题就可以转化为 "找满足条件的转折点个数 "

代码如下:

#include<iostream>
#include<cstdio>
int high[100005];    //存储花的高度
int main()
{
    int n,ans=1,i;   //ans保存最长的序列,因为第一个位置的花,不过锯齿形状如何,始终能留下来,初始值为1
    scanf("%d",&n);
    for(int i=1;i<=n;i++)   scanf("%d",high+i);
    int flag=-1;    //flag表示满足条件的标识,flag=1表示满足条件A了,flag=0表示满足条件B
    for(int i=2;i<=n;i++)
    {
        if(high[i]>high[i-1]&&flag!=1)  //由于要得到锯齿形的队形,因此当前位置与前一个位置的高度关系应该是
        {//满足条件A时,序列长度++      //条件A和B交替满足,如果连续满足条件A,或者连续满足条件B都不应该做任何计数(缩点)
            ans++;                      //条件交替满足的意思是比如 P Q S 是一个合法序列,那么 P与 Q满足A,S与P必须满足B
            flag=1;
        }
        if(high[i]<high[i-1]&&flag!=0)
        {//满足条件B时,序列长度++
            ans++;
            flag=0;
        }
    }
    printf("%d\n",ans);
    return 0;
}
上一篇:Linux命令:who


下一篇:Exchange 2013\2016共存邮箱登录报错