• 欢迎光临~

Codeforces Round #809 (Div. 2) C. Qpwoeirut And The City(枚举 / dp)

开发技术 开发技术 2022-08-03 次浏览

https://codeforces.com/contest/1706

一排n栋建筑,其中第I(1≤I≤n)栋楼高hi层。当且仅当建筑物I中的层数hi大于建筑物j中的层数hj时,建筑物I才比建筑物j高

如果建筑I高于建筑I-1和建筑i+1(并且两者都存在),则建筑I是凉爽的。注意1号楼和n号楼都不能凉。

为了改造这个城市,Qpwoeirut需要最大化酷建筑的数量。为此,Qpwoeirut可以在任何建筑的顶部建造额外的楼层,使它们更高。请注意,他不能删除已经存在的楼层。

由于建造新的楼层很昂贵,Qpwoeirut希望尽量减少他建造的楼层数量。找出Qpwoeirut需要建造的最少楼层数,以便最大化酷建筑的数量。
  • 简而言之,在最大化凸包数量的基础上,最小化增加建筑的数量
input
6
3
2 1 2
5
1 2 1 4 3
6
3 1 4 5 5 2
8
4 2 1 3 5 3 6 1
6
1 10 1 1 10 1
8
1 10 11 1 10 11 10 1
output
2
0
3
3
0
4
  1. 第一种模拟做法
  • 例1和例2可见,当n为奇数时,要想最大化凸包的数量,就是固定的,每隔一个就必须为凸包,不然达不到最大凸包的数量

  • 当n为偶数时,可以看到最大化凸包数量就是n-1/2个,因为在奇数的基础上多了一个,并不能多构成一个凸包
    所以偶数时的数量是跟n-1的奇数时是一样的,但是问题就在于多了一个点
    如何在m=(n-1)/2个中都找到合适的最小值?

  • 可以知道它只是多了一个值,所以在m-1次的正常凸包中,会有两个数据之间隔了一个数
    也就是有的是m-1个是相连的,但是有一个是分开的
    我们就可以枚举它的出现位置
    从后往前
    Codeforces Round #809 (Div. 2) C. Qpwoeirut And The City(枚举 / dp)

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
const int N=500500;
const int M=2002;
LL a[N],b[N];
int f[N][2][2];
LL dp[N][3];
int main()
{
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
    int T=1;
    cin>>T;
    while(T--)
    {
        LL n;
        cin>>n;
        for(LL i=1;i<=n;i++)
            cin>>a[i];
        LL sum=0;
        for(LL i=2;i<=n-1;i++)
        {
            b[i]=max((LL)0,max(a[i-1],a[i+1])+1-a[i]);
            if(i%2==0) sum+=b[i];
            //cout<<b[i]<<" ";
        }
        if(n%2==1) cout<<sum<<endl;
        else
        {
            LL minn=sum;
            LL res=sum;
            for(LL i=n-1;i>=2;i-=2)
            {
                res-=b[i-1];
                res+=b[i];
                minn=min(res,minn);
            }
            cout<<minn<<endl;
        }
    }
    return 0;
}

dp做法稍后再补

喜欢 (0)