題目鏈接：點擊查看

題目大意：給出 $n$ 個問題，每個問題有如下屬性：

$tag$：標簽

$c$：困難度

$s$：獎勵值

初始時 $c_i=2^i$，初始時 $IQ=0$ ，假設 $last$ 是最后一個回答的問題，則需要滿足 $|c_i?c_{last}|>IQ$ 才可以回答問題 $i$，且回答之后會發生的變化：

$IQ=|c_i?c_{last}|$

獲得 $|s_i?s_{last}|$ 的獎勵

$last$ 變成 $i$

可以以任意順序回答任意問題任意次，問最大可以獲得的獎勵值是多少

題目分析：動態規劃問題，先不考慮題目限制，一開始設計的狀態是 $d{p}_{i,j}$ ，指倒數第二次回答的是問題 $i$ ，最后一次回答的是問題 $j$ 的最大貢獻，正確性顯然，但是轉移的方程好像有點爆

不過仔細觀察狀態之間的轉移，若 $d{p}_{i,j}$ 想要轉移到 $d{p}_{j,k}$，當且僅當 $|c_k?c_i|>|c_i?c_j|$ 才行

將模型放到圖論上去，就變成了：有 $n$ 個點，任意兩點之間都可以建邊，且邊權為 $|c_i?c_j|$ 的一個無向圖，那么我們可以在無向圖上從小邊權向大邊權進行迭代，這樣復雜度就下來了

簡單來說就是設計 $d{p}_i$ 為最后一個回答的問題是 $i$ 的最大貢獻，當迭代到 $(i,j)$ 這條邊時， 狀態 $i$ 可以由狀態 $j$ 更新，同時狀態 $j$ 也有可能被狀態 $i$ 更新（因為是無向圖），所以轉移方程如下：設 $val=|s_i?s_j|$

• $d{p}_i=max(d{p}_i,d{p}_j+val)$
• $d{p}_j=max(d{p}_j,d{p}_i+val)$

到此為止，我們還需要解決兩個問題：

邊權有相同的該怎么辦

如何按照邊權從小到大枚舉邊

關于第一點比較好論述，因為所有的邊權都是諸如 $|2^i?2^j|$ 的形式，將其轉換為二進制后不難發現，這個值在區間 $[i,j?1]$ 的位置都是 $1$，其他位置都是 $0$，所以對于任意一對互不相同的 $(i,j)$ 二元對來說，其權值都是互不相同的

關于第二點，因為題目內存的限制，使得我們沒辦法將所有的邊都存下來然后排序，但是，假如我們可以將邊存下來然后排序的話又能怎樣？二進制遞增的速度非?？?#xff0c;以至于當 $n$ 較大的時候，數值根本存不下，手玩一下找一下規律，不難發現二元對 $(i,j)$ 權值的大小（假設 $i<j$），由 $j$ 主導，當 $j$ 相同的時候，權值大小與 $i$ 呈負相關的關系

所以在按照權值大小枚舉所有邊的時候，可以按照：

從 $2?n$ 枚舉 $j$

從 $j?1$ 枚舉 $i$

按照上述順序去枚舉所有的二元對 $(i,j)$ ，就可以滿足枚舉的邊權是從小到大的了

代碼：

// Problem: D. Genius // Contest: Codeforces - Codeforces Round #708 (Div. 2) // URL: https://codeforces.com/contest/1497/problem/D // Memory Limit: 32 MB // Time Limit: 2000 ms // // Powered by CP Editor (https://cpeditor.org)// #pragma GCC optimize(2) // #pragma GCC optimize("Ofast","inline","-ffast-math") // #pragma GCC target("avx,sse2,sse3,sse4,mmx") #include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> #define lowbit(x) x&-x using namespace std; typedef long long LL; typedef unsigned long long ull; template<typename T> inline void read(T &x) {T f=1;x=0;char ch=getchar();while(0==isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}while(0!=isdigit(ch)) x=(x<<1)+(x<<3)+ch-'0',ch=getchar();x*=f; } template<typename T> inline void write(T x) {if(x<0){x=~(x-1);putchar('-');}if(x>9)write(x/10);putchar(x%10+'0'); } const int inf=0x3f3f3f3f; const int N=5e3+100; LL dp[N],tag[N],s[N]; int main() { #ifndef ONLINE_JUDGE // freopen("data.in.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);int w;cin>>w;while(w--) {memset(dp,0,sizeof(dp));int n;read(n);for(int i=1;i<=n;i++) {read(tag[i]);}for(int i=1;i<=n;i++) {read(s[i]);}for(int j=2;j<=n;j++) {for(int i=j-1;i>=1;i--) {if(tag[i]==tag[j]) {continue;}LL dpi=dp[i],dpj=dp[j],val=abs(s[i]-s[j]);dp[i]=max(dp[i],dpj+val);dp[j]=max(dp[j],dpi+val);}}cout<<*max_element(dp,dp+n+1)<<endl;}return 0; } 超強干貨來襲 云風專訪：近40年碼齡，通宵達旦的技術人生

總結

以上是生活随笔為你收集整理的CodeForces - 1497D Genius(dp)的全部內容，希望文章能夠幫你解決所遇到的問題。

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