正题

---

题目大意

一个序列$A$可以每次选择一段区间$(A_i+1)\%4(i\in [l..r])$。求最少次数使其变成$B$序列。

---

解题思路

先计算出每个数字最少加多少可以变成目标数字记录入$a$数组。

然后若不考虑一个数要取模多次的话答案就是 $$\sum _{i=1}^n\max \{a_i-a_{i-1},0\}(a_0=0)$$

但是这道题变成了每个柱子的高度是$4k_i+a_i(k\in \mathbb{N})$ 那么我们考虑若一段区间$[l..r]$的$k$要加1会更优那么有 $$a_l-a_{l-1}+4<a_{r+1}-a_r$$ 那么答案就可以减去$$(a_{r+1}-a_r)-(a_l-a_{l-1}+4)$$ 那么我们枚举$r$，开个桶来计算$l$

---

$code$

#include<cstdio> #include<algorithm> #include<cstring> using namespace std; const int N=101000; int T,n,a[N],ans=2147483647,t[5]; int main() { scanf("%d",&T); while(T--) { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); memset(t,0,sizeof(t)); ans=0; for(int i=1;i<=n;i++){ int val; scanf("%d",&val); a[i]=(val-a[i]+4)%4; ans+=max(a[i]-a[i-1],0); } for(int i=2;i<=n;i++){ int c=a[i]-a[i-1]; if(c>0){ if(t[1]&&c>1) t[1]--,t[c]++,ans-=c-1; else if(t[2]&&c>2) t[2]--,t[c]++,ans-=c-2; } else t[c+4]++; } printf("%d\n",ans); } }