一、題目

點此看題

二、解法

玄學警告?，由于線上的數量是定值，轉而求線的數量已推知線下數量。

設$t[i]$為$i$時刻線的數量，$d[i]$為線下的數量，易知 $t[i]=m[i]+d[i]+1$，有這樣一些限制：

• $t[i]\ge t[i?1]$，即線的數量單調遞增
• $t[i]\ge m[i]$，這個看定義吧
• $t[i]?1\le t[i?1]$，即每天只能畫一條線

前兩個限制取最大值，第三個限制從后往前掃，把$t[i]$和$t[i+1]?1$取$max$，最后掃一遍就可以算出答案，時間復雜度$O(n)$。

那么這個算法的正確性如何推知呢？我的理解是我們盡可能貼著$1,2$限制的邊界也就是盡量把線畫重，因為線的數量越少越好，后面我們要掃回來的原因是我們貼著邊界畫不一定畫的出來合法解，我們需要把以前畫重的線拆開，以滿足后面的需要。

#include <cstdio> #include <iostream> #define int long long using namespace std; const int M = 100005; int read() {int x=0,flag=1;char c;while((c=getchar())<'0' || c>'9') if(c=='-') flag=-1;while(c>='0' && c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();return x*flag; } int n,ans,m[M],t[M]; signed main() {n=read();for(int i=1;i<=n;i++)t[i]=max(t[i-1],(m[i]=read())+1);for(int i=n-1;i>=1;i--)if(t[i+1]-1>t[i])t[i]=t[i+1]-1;for(int i=1;i<=n;i++)ans+=t[i]-m[i]-1;printf("%lld\n",ans); }

總結

以上是生活随笔為你收集整理的CF924C Riverside Curio的全部內容，希望文章能夠幫你解決所遇到的問題。

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