CF1706C题解

分数可能是不支持的，所以用了另一种方法表示

题目大意

给你 \(n\) 座楼房的高度，求最多的能拥有的cool building的数量。

分析

本题可以视为一道比较简单的线性动态规划题目。

首先，我们分析 \(n\) 是奇数时的情况。

当 \(n\) 是奇数时，可以得出最多可以拥有的cool building的数量是 $ (n-1)/2 $，即每一个偶数位的楼房都可以成为cool building。（因为题目要求成为cool building的要求是比左右两座楼房都高，所以连续的两座楼房不能同时成为cool building。）

本段代码 ：

long long sum=0;
for(long long i=2;i<=n-1;i+=2) {
    sum+=((a[i]>a[i-1] && a[i]>a[i+1])?0:max(a[i-1],a[i+1])+1-a[i]);
}
write(sum),putchar(10);//write是快速输出函数，下同

接下来，我们分析 $ n $ 是偶数时的情况。

当 $ n $ 是奇数时，可以得出最多可以拥有的cool building的数量是 $ $。 即对于任何 \(i\) , 当 $ i < n $ 且 $ i $ 是偶数时，$ i $ 和 $ i+1 $ 中必定有一个被选。

对于上方 偶数 的解释：如果当 $ i $ 是偶数时且 $ i $ 和 $ i+1 $ 处都没有被选，那么当前问题就会退化为长度是 \(n-2\) 序列的问题。但当 $ i $ 是奇数时且 $ i $ 和 $ i+1 $ 处都没有被选，例如当1 2 3 4 2 1的第 $ 3 $ 个和第 $ 4 $ 个都没有被选时，可以选择第 $ 2 $ 个和第 $ 5 $ 个，符合连续的两座楼房不能同时成为cool building这个要求。

然后就可以证明 $ n $ 是偶数时，$ i $ 是奇数时且 $ i $ 和 $ i+1 $ 处都没有被选是有可能可以获得最大的cool building的数量了。

接下来就是动态规划的过程，可以设 $ 1 $ 为选择该建筑，$ 0 $ 为不选。

设连续 $ 2 $ 座建筑不太好转移，于是我们设连续 $ 4 $ 座建筑，有 $ 3 $ 种情况，分别是1 0 0 1、1 0 1 0、0 1 0 1，分别表示的内容如下所示。

1 0 0 1：对于连续的 $ 4 $ 座建筑，选择第 $ 1 $ 座和第 $ 4 $ 座，让它们变为 cool buildings。

0 1 0 1：对于连续的 $ 4 $ 座建筑，选择第 $ 2 $ 座和第 $ 4 $ 座，让它们变为 cool buildings。

1 0 1 0：对于连续的 $ 4 $ 座建筑，选择第 $ 1 $ 座和第 $ 3 $ 座，让它们变为 cool buildings。

每一种状态的转移，就是在上一次的转移结果中寻找与当前状态前两位相同的后两位的所有结果中的最小值加上当前状态需要变为 cool building 的建筑需要添加的楼层数。

可能讲的不太清楚，那么举个例子：

0 1 0 1状态的转移，就是寻找状态末两位是0 1的所有状态对其上一次结果进行转移，就是在上一次的结果中选取1 0 0 1和0 1 0 1中需要添加的楼层数较小的那一个进行转移。

状态转移方程详见代码及注释，注意 $ n = 4 $ 时需要特判。

本段代码 ：

long long ct[100005]={};
for(long long i=2;i<=n-1;++i) ct[i]=((a[i]>a[i-1] && a[i]>a[i+1])?0:max(a[i-1],a[i+1])+1-a[i]);
if(n==4) {
write(min(ct[2],ct[3])),putchar(10);
    return ;//这是在void函数内
}
memset(dp,0,sizeof dp);
dp[1][0]=ct[3]+ct[5];
dp[1][1]=ct[2]+ct[5];
dp[1][2]=ct[2]+ct[4];//以上为预处理，因为其中对 ct 数组的引用超过了 4，所以 n = 4 时需要特判
long long i,j;
for(i=6,j=2;i+2<=n;i+=2,++j) {//以下二进制展开后的第 3 位代表 i 
    dp[j][0]=min(dp[j-1][1],dp[j-1][0])+ct[i+1];//0 代表 5，即 0 1 0 1，选 i + 1
    dp[j][1]=dp[j-1][2]+ct[i+1];//1 代表 9，即 1 0 0 1，选 i + 1
    dp[j][2]=dp[j-1][2]+ct[i];//2 代表 10，即 1 0 1 0，选 i
}
write(min(min(dp[j-1][0],dp[j-1][1]),dp[j-1][2])),putchar(10);

这种思路代码简单，核心代码总共不到 $ 20 $ 行，但是可能不太容易理解，如果有更容易理解的表达或文章有误请在下方留言。