自动搬运

查看原文

来自洛谷，原作者为

	czh1005 https://www.luogu.com.cn/record/220917087

搬运于2025-08-24 23:13:44，当前版本为作者最后更新于2025-04-18 11:30:13，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

这道题很明显是 dp，最开始想的是一维状态。
$dp_{i}$ 表示前 $i$ 个字符串拼起来的最小长度。
但发现这样子就不知道上一个字符串翻没翻转。
所以加一个维度。
$dp_{i,0/1}$ 表示前 $i$ 个字符串拼起来，如果是 $0$ 表示第 $i$ 个字符串不进行翻转，如果是 $1$ 表示第 $i$ 个字符串进行翻转的最小长度。
每个字符串用 $a_{i}$，$b_{i}$ 表示。
转移方程：\

$$dp_{i,0} \gets \min(dp_{i-1,0}+2-[b_{i-1}=a_{i}],dp_{i-1,1}+2-[a_{i-1}==a_{i}])$$\ $$dp_{i,1} \gets \min(dp_{i-1,0}+2-[b_{i-1}=b_{i}]),dp_{i-1,1}+2-[a_{i-1}==b_{i}])$$\ 代码: ```cpp #include using namespace std; const int maxn=1e5+10; int n,dp[maxn][2]; char a[maxn],b[maxn]; int main(){ cin>>n; for(int i=1;i<=n;i++) cin>>a[i]>>b[i]; dp[1][0]=dp[1][1]=2;//初始化 for(int i=1;i<=n;i++){ //转移方程 dp[i][0]=min(dp[i-1][0]+(b[i-1]==a[i]?1:2), dp[i-1][1]+(a[i-1]==a[i]?1:2)); dp[i][1]=min(dp[i-1][0]+(b[i-1]==b[i]?1:2), dp[i-1][1]+(a[i-1]==b[i]?1:2)); } cout<<min(dp[n][0],dp[n][1])<<'\n';//输出答案 return 0; } ```$$