正題

---

題目大意

一個序列$A$可以每次選擇一段區(qū)間$(A_i+1)\%4(i\in [l..r])$。求最少次數(shù)使其變成$B$序列。

---

解題思路

先計算出每個數(shù)字最少加多少可以變成目標數(shù)字記錄入$a$數(shù)組。

然后若不考慮一個數(shù)要取模多次的話答案就是
$$\sum _{i=1}^n\max \{a_i?a_{i?1},0\}(a_0=0)$$

但是這道題變成了每個柱子的高度是$4k_i+a_i(k\in \mathbb{N})$
那么我們考慮若一段區(qū)間$[l..r]$的$k$要加1會更優(yōu)那么有
$$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);} } 創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結

以上是生活随笔為你收集整理的jzoj4788-[NOIP2016提高A组模拟9.17]序列【差分,贪心】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。