昨天晚上寫的時候看錯題了，以為并不是交替走，最后沒時間了讀了一遍題目發現是交替走，然后就秒了但是已經沒時間寫了。

其實昨天并不想寫，不過看了下D題發現是個數學題，雖然我數學題非常渣渣，但是拿起筆就推了推式子，發現可做，寫完代碼后第一次交RE，數組開小了，第二次交Wa，很奇怪，最后發現預處理應該是$2\times 10^6$，非常蛋疼~

---

C. Minimum Grid Path

預處理前綴和以及前綴最小值，由于是交替走，只有兩種情況：兩個方向都走$k$次，或者一個方向走$k+1$次一個方向走$k$次，枚舉$k$計算即可。

#include<cstring> #include<iostream> #include<algorithm> using namespace std; using ll=long long; constexpr int N=200010; int n; ll c[N]; ll a[N],b[N]; ll sa[N],sb[N]; ll ma[N],mb[N]; int cnta,cntb; ll calc(int k) {ll res=1e18;res=min(res,sa[k]+ma[k]*(n-k)+sb[k]+mb[k]*(n-k));if(k+1<=cnta) res=min(res,sa[k+1]+ma[k+1]*(n-k-1)+sb[k]+mb[k]*(n-k));return res; } int main() {ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);int T=1;cin>>T;while(T--){cin>>n;for(int i=1;i<=n;i++) cin>>c[i];cnta=cntb=0;for(int i=1;i<=n;i+=2) a[++cnta]=c[i];for(int i=2;i<=n;i+=2) b[++cntb]=c[i];sa[0]=sb[0]=0;for(int i=1;i<=cnta;i++) sa[i]=sa[i-1]+a[i];for(int i=1;i<=cntb;i++) sb[i]=sb[i-1]+b[i];ma[0]=mb[0]=1e18;for(int i=1;i<=cnta;i++) ma[i]=min(ma[i-1],a[i]);for(int i=1;i<=cntb;i++) mb[i]=min(mb[i-1],b[i]);ll res=1e18;for(int i=1;i<=min(cnta,cntb);i++) res=min(res,calc(i));cout<<res<<'\n';}return 0; }

總結

以上是生活随笔為你收集整理的C. Minimum Grid Path（思维）的全部內容，希望文章能夠幫你解決所遇到的問題。

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