sharpland的博客
我们设 $f[i][j]$ 为让原字符串满足最多包含 $\texttt{hard}$ 的前 $j$ 个字符，所需要的最小修改代价
特别的， $f[i][0]$ 表示不包含 $h$ 的最小修改代价
考虑转移方程，有两种情况
当 $s[i] \ne c[j+1]$ 时（ $c$ 是预先处理好的 $\texttt{hard}$ ），加上第 $i$ 个字符后不会增加最大匹配的长度，所以 $f[i][j]=f[i-1][j]$
当 $s[i] = c[j+1]$ ，又可以选择删与不删第 $i$ 个字符
所以 $f[i][j]=\min(f[i-1][j]+a[i],f[i-1][j-1])$
在选择不删除的时候，为了不凑出 $\texttt{hard}$ 的前 $j+1$ 个字符，我们在前面最多只能凑出前 $j-1$ （使得 $c[j+1]$ 与前面的字符断开）。
我们发现在每次转移的时候，只用到了 $f[i-1]$ 和 $f[i]$ 这两层，所以我们可以把第一维用滚动数组省略掉。
#include<cstdio>
#include<iostream>
using namespace std;
const long long Maxn=100000+10,inf=(1ll<<60);
long long f[5],a[Maxn];
char c[5]={'f','h','a','r','d'};
char s[Maxn];
long long n,ans=inf;
int main()
{
// freopen("in.txt","r",stdin);
scanf("%lld",&n);
scanf("%s",s+1);
for(long long i=1;i<=n;++i)
scanf("%lld",a+i);
for(long long i=1;i<=n;++i)
for(long long j=3;j>=0;--j)
if(s[i]==c[j+1])
{
f[j]+=a[i];
if(j)f[j]=min(f[j],f[j-1]);
}
for(long long i=0;i<4;++i)
ans=min(ans,f[i]);
printf("%lld\n",ans);
return 0;
}显然调整到相邻高度最优
考虑dp，显然修改$a_i$时可直接转移
考虑滚动数组以降低空间复杂度，故设如下状态
设$f_{i,j,0}$表示已经建了j座房子，且最后一座在第$i-1$个位置之前的最小次数
$f_{i,j,1}$表示已经建了j座房子，且最后一座在第i个位置的最小次数
$f_{i,j,2}$表示已经建了j座房子，且最后一座在第$i-1$个位置的最小次数
则可得转移 $$ f_{i,j,0}=min(f_{i-1,j,0},f_{i - 1,j,2}) $$
$$ f_{i,j,1}=min(f_{i,j-1,0}+max(0,a_{i-1}-a_i+1),f_{i,j-1,2}+max(0,min(a_{i-1},a_{i-2}-a_i+1))) $$
$$ f_{i,j,2}=f_{i-1,j,1}+max(0,a_i-a_{i-1}+1) $$
注：$max(0,x)$表示如果差大于0则调整，否则无需调整
滚动数组转移即可，注意滚动数组后转移需注意实现细节
固定第一个格子的颜色。
我们发现如果只有一行的话涂色总数是斐波那契数列，
当行数更多时，分两种情况：
第一行是$10101010$即没有相邻颜色时，竖着可以看成另一个斐波那契数列。
第一行是$11001100$有相邻颜色时，下一行只能是对应的不同颜色。
所以答案就是$(F[n] + F[m] - 1)\times 2$
Server time: 2025-06-08 04:10:09 | Maintainer: CSQ@WHU