D. Geniue

Frozen_Guardian題解
Implicit_總結(jié)
首先把此序列看作一個完全圖，然后按照邊權(quán)從小到大的順序枚舉邊。

如何按照邊權(quán)從小到大枚舉邊?
下面考慮形如邊$(a,b)$都默認$a<b$。

任意考慮兩條邊$(a,b)$和$(c,d)$，不難發(fā)現(xiàn)只要有$b<d$，一定有$c_{a,b}<c_{c,d}$，而對于較大的點相同的情況比如$(a,i)$和$(b,i)$，顯然如果$a<b$那么有邊權(quán)$c_{a,i}>c_{b,i}$。
于是如果想要從小到大枚舉邊權(quán)只需要從小到大枚舉$i$，從大到小枚舉$j$

設(shè)計dp：
狀態(tài)表示：$f_i$表示以$i$節(jié)點結(jié)尾時的最大值

狀態(tài)轉(zhuǎn)移：$$\{\begin{array}{l}{f}_i=\max \{f_i,f_j+|s_i?s_j|\}\\ f_j=\max \{f_j,f_i+|s_i?s_j|\}\end{array}$$

#include<cstring> #include<iostream> #include<algorithm> using namespace std; using ll=long long; constexpr int N=200010; ll dp[N],s[N],tag[N]; int n; 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>>tag[i];for(int i=1;i<=n;i++) cin>>s[i];memset(dp,0,sizeof(ll)*(n+1));// i從小打到枚舉 而i相同從大到小枚舉j 保證邊是從小到大枚舉 本質(zhì)枚舉邊for(int i=1;i<=n;i++)for(int j=i-1;j>=1;j--)if(tag[i]!=tag[j]){ll dpj=dp[i]+abs(s[i]-s[j]);ll dpi=dp[j]+abs(s[i]-s[j]);dp[i]=max(dp[i],dpi);dp[j]=max(dp[j],dpj);}cout<<*max_element(dp+1,dp+1+n)<<'\n';}return 0; }

總結(jié)

以上是生活随笔為你收集整理的codeforces1497 D. Geniue（dp+图论）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。