51nod 1281山峰和旗子

1281 山峰和旗子

题目来源： Codility

基准时间限制：1 秒空间限制：131072 KB 分值: 40 难度：4级算法题

用一个长度为N的整数数组A，描述山峰和山谷的高度。山峰需要满足如下条件， 0 < P < N - 1 且 A[P - 1] < A[P] > A[P + 1]。

现在要在山峰上插上K个旗子，并且每个旗子之间的距离 >= K，问最多能插上多少个旗子（即求K的最大值）。两个山峰之间的距离为|P - Q|。

以上图为例，高度为：1 5 3 4 3 4 1 2 3 4 6 2。其中可以作为山峰的点为：1 3 5 10。

放2面旗子, 可以放在1 和 5。

放3面旗子, 可以放在1 5 和 10。

放4面旗子, 可以放在1 5 和 10，之后就放不下了。

所以最多可以放3面旗子。

Input

第1行：一个数N，表示数组的长度(1 <= N <= 50000)。

第2 - N + 1行：每行1个数Ai(1 <= Ai <= 10^9)。

Output

输出最多能插上多少面旗子（即求K的最大值）。

Input示例

Output示例

3

思路：二分+dp-------用一个f[]数组保存山峰的位置，首先如果没有山峰则直接输出0,其次距离越大代表我们要插的旗子数就越大，我们枚举旗子的个数k 找到最大的可行方案；当然直接枚举会超时，所以这里需要用二分来枚举;
　　　对于每一个k我们需要用一次dp数组来遍历一次，dp[i]代表前i个位置能插入距离为k的旗子的个数;我们可以得到递推公式 若当前位置不可以插旗子dp[i] = dp[i-1];否则dp[i] = max(dp[i-k]+1,dp[i]);
　　　其中i-k>0；遍历完之后若dp[n-1]>=k说明我们的k还可以继续增大，直到dp[n-1]恰好等于k的时候就停止二分，此时的k即为最大值

 #include<iostream>

 #include<algorithm>

 #include<cstring>

 #include<cstdio>

 using namespace std;

 typedef long long LL;

 const int maxn = ;

 LL n,a[maxn],f[maxn],d[maxn];;

 int main()

 {

     ios::sync_with_stdio(false);

 //    freopen("in.txt","r",stdin);

     while(cin>>n){

         int flag = ;

         for(int i=;i<n;i++)cin>>a[i];

         for(int i=;i<n-;i++)

             if(a[i]>a[i-]&&a[i]>a[i+]){

                 f[i] = ;flag++;

             }

         if(!flag){

             cout<<""<<endl;

             continue;

         }

         int l=,r=n,ans=;

         while(l<r){

             int k = (l+r)>>;

             for(int i=;i<n;i++)

                 d[i] = f[i];

             for(int i=;i<n;i++){

                 if(!f[i])d[i]=d[i-];

                 else if(i-k>) d[i] = max(d[i-k]+,d[i]);

             }

             if(d[n-]>=k){

                 ans = k;

                 l = k+;

             }else r = k;

         }

         cout<<ans<<endl;

     }

     return ;

 }

巴特西

51nod 1281山峰和旗子

最新文章

热门文章