CF1497D Genius

題意：

n個問題從i到n編號，第i個問題給出的$c_i=2^i,ta{g}_i,s_i$
解決問題i后解決問題j條件是：IQ<|$c_i?c_j$|,同時獲得|$s_i?s_j$|分
問題解決得次數和順序不受限制
一開始IQ=0，求最高可獲得得分數
內存限制31.25MB，大致可以開1e7的數組

題解：

很明顯動態規劃，按照一般思路設dp[i][j]：上一次是第i個問題，本次是第j個問題的最大貢獻。但是很明顯空間不夠
對于dp[][]的狀態轉移，當且僅當$|c_k?c_j|>|c_i?c_j|$,可以從$d{p}_{i,j}$轉移到$d{p}_{j,k}$
我們將這個$|c_i?c_j|$放在圖論上分析，就是有n個點，任意兩點之間建邊，邊權為$|c_i?c_j|$的一個無向圖，我們可以在無向圖商從小邊權向大邊權轉移，這樣就可以不用二維來轉移，降低空間復雜度
設$d{p}_i$表示最后一個問題是i的最大貢獻，當我們走(i,j)這條邊時，狀態i可以由狀態j更新，同理，狀態j也可以由狀態i更新，因為這是無向邊。
有轉移方程：
$val=|s_i,s_j|$
$tm{p}_i=d{p}_i$
$tm{p}_j=d{p}_j$
$d{p}_i=max(d{p}_i,tm{p}_j+val)$
$d{p}_j=max(d{p}_j,tm{p}_i+val)$
不過問題還沒完全解決，現在我們還要考慮幾個問題：

邊權一樣，優先級順序？

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

因為$c_i=2^i$,邊權都是$|2^i?2^j|$的形式，說明對于任意不同的(i,j)，所對應的邊也一定不同。也就是不會有邊權一樣的邊
對于第二個問題，因為有空間的限制，我們不可以存下所有邊然后排序。此時我們觀察(i,j)權值的變化情況，假設i<j，權值二進制狀態下區間[i,j-1]的位置都是1，說明當j越大時，權值越大，當j一樣時，i越小權值越大
那么我們就看這樣枚舉點對(i,j),先枚舉j，從小到大，然后枚舉i，從大到小，這樣枚舉出來的邊權保證從小到大

代碼：

#include <bits/stdc++.h> #include <unordered_map> #define debug(a, b) printf("%s = %d\n", a, b); using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> PII; clock_t startTime, endTime; //Fe~Jozky const ll INF_ll= 1e18; const int INF_int= 0x3f3f3f3f; void read(){}; template <typename _Tp, typename... _Tps> void read(_Tp& x, _Tps&... Ar) {x= 0;char c= getchar();bool flag= 0;while (c < '0' || c > '9')flag|= (c == '-'), c= getchar();while (c >= '0' && c <= '9')x= (x << 3) + (x << 1) + (c ^ 48), c= getchar();if (flag)x= -x;read(Ar...); } 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'); } void rd_test() { #ifdef ONLINE_JUDGE #elsestartTime= clock();freopen("data.in", "r", stdin); #endif } void Time_test() { #ifdef ONLINE_JUDGE #elseendTime= clock();printf("\nRun Time:%lfs\n", (double)(endTime - startTime) / CLOCKS_PER_SEC); #endif } const int maxn= 5e3 + 9; ll tag[maxn]; ll s[maxn]; ll dp[maxn]; int x[maxn][maxn]; int main() {//rd_test();int t;read(t);while (t--) {int n;cin >> n;memset(dp, 0, sizeof(dp));for (int i= 1; i <= n; i++)cin >> tag[i];for (int i= 1; i <= n; i++)cin >> s[i];for (int j= 2; j <= n; j++) {for (int i= j - 1; i >= 1; i--) {if (tag[i] == tag[j])continue;ll tmpi= dp[i];ll tmpj= dp[j];ll val= abs(s[i] - s[j]);dp[i]= max(dp[i], tmpj + val);dp[j]= max(dp[j], tmpi + val);}}ll maxx= 0;for (int i= 1; i <= n; i++) {maxx= max(maxx, dp[i]);}cout << maxx << endl;}//Time_test(); }

總結

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

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