Bishops Alliance—— 最大上升子序列

原題鏈接:http://codeforces.com/gym/101147/problem/F

題意:n*n的棋盤,給m個主教的坐標及其私有距離p,以及常數C,求位于同一對角線上滿足條件:dist(i, j) >= p[i]^2 + p[j]^2 + C?

的主教集合的元素個數最大值。

解題思路

上述條件可以等價為:

  d(j) - d(i) +1 >= p[i]^2 + p[j]^2 + C ?  // d(i) 為第i個主教相對于該對角線頂點的距離

  d(j) - p[j]^2 - C + 1>= d(i) + p[i]^2

設 f(i) = d(i) + p[i] ^2, ?g(i) = d(i) - p[i]^2 - C + 1?

下面考慮一條對角線,設 c[x] ?為長度為x 的最后一個主教編號,例如c[len] = i ?代表長度為len的防線最后一個主教編號為i。

(特別的,c[0] = 0,?f(0) = -INF )

首先將該對角線上的主教按 d(i) 排序, len 為當前最大長度+1,依次查詢每一個主教并同時更新最大長度, 偽代碼如下:

  對當前查詢的主教u

    j = lower_bound(c, c+len,u,cmp) - c

    if ?j =len && g(u) >= f(c[j-1])?

      c[len++] = u

    if ?j != len && ?g(u) >= f(c[j-1])?

      c[j] = u

注意: 數據范圍為 LL

代碼如下:

 1 #include <cstring>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <vector>
 5 using namespace std;
 6 const int maxn = 100000+10;
 7 typedef long long LL;
 8 #define INF 999999999999999999LL
 9 vector<int> D1[2*maxn];
10 vector<int> D2[2*maxn];
11 
12 int c[maxn];
13 int row[maxn], col[maxn], p[maxn];
14 int n, m, C;
15 //計算對角線編號
16 int dig_id1(int x, int y) {return x-y+n;}
17 int dig_id2(int x, int y) {return x+y;}
18 
19 int d1(int i) {return min(row[i], col[i]);}
20 int d2(int i) {return min(n-row[i]+1, col[i]);}
21 
22 LL f1(int i) {return !i ? -INF : d1(i) + LL(p[i])*p[i];}
23 LL f2(int i) {return !i ? -INF : d2(i) + LL(p[i])*p[i];}
24 
25 LL g1(int i) {return d1(i) - LL(p[i])*p[i] - C + 1;}
26 LL g2(int i) {return d2(i) - LL(p[i])*p[i] - C + 1;}
27 
28 bool cmpd1(int i, int j) {return d1(i) < d1(j);}
29 bool cmpd2(int i, int j) {return d2(i) < d2(j);}
30 bool cmp1(const int& a,const int& b) {return f1(a) < f1(b);}
31 bool cmp2(const int& a,const int& b) {return f2(a) < f2(b);}
32 LL (*f[])(int) ={
33      f1,
34     f2
35  };
36 LL (*g[])(int) = {
37     g1,
38     g2
39 };
40 bool (*cmp[])(const int& ,const int& ) = {
41     cmp1,
42     cmp2
43 };
44 
45 int cal(vector<int> &D,int flag) {
46     if(!D.size()) return 0;
47     if(flag == 0) sort(D.begin(), D.end(), cmpd1);
48     else sort(D.begin(), D.end(), cmpd2);
49     for(int i = 0; i <= D.size(); i++) c[i] = 0;
50     int len = 1;
51     int j;
52     for(int i = 0; i < D.size(); i++){
53         int u = D[i];
54         j = lower_bound(c, c+len, u, cmp[flag]) - c;
55         if(j == len && g[flag](u) >= f[flag](c[j-1])) {
56             c[len++] = u;
57         }
58         if(j != len && g[flag](u) >= f[flag](c[j-1])) {
59             c[j] = u;
60         }
61     }
62     return len - 1;
63 }
64 #define fin stdin
65 int main() {
66 //    FILE * fin;
67 //    fin =  fopen("bishops.in", "r");
68     int T;
69     fscanf(fin, "%d", &T);
70     while(T--) {
71         fscanf(fin, "%d%d%d", &n, &m, &C);
72         for(int i = 0; i <= 2*n; i++) D1[i].clear();
73         for(int i = 0; i <= 2*n; i++) D2[i].clear();
74         for(int i = 1; i <= m; i++) {
75             fscanf(fin, "%d%d%d", &row[i], &col[i], &p[i]);
76             int id1 = dig_id1(row[i], col[i]);
77             int id2 = dig_id2(row[i], col[i]);
78             D1[id1].push_back(i);
79             D2[id2].push_back(i);
80         }
81         int ans = 0;
82         for(int i = 0; i <= 2*n; i++) {
83             ans = max(ans, cal(D1[i], 0));
84             ans = max(ans, cal(D2[i], 1));
85         }
86         printf("%d\n", ans);    
87     }
88     return 0;
89 }

?

轉載于:https://www.cnblogs.com/Kiraa/p/6089377.html

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:http://www.pswp.cn/news/253933.shtml
繁體地址,請注明出處:http://hk.pswp.cn/news/253933.shtml
英文地址,請注明出處:http://en.pswp.cn/news/253933.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

LeGO-LOAM學習

前言 在學習了LOAM之后&#xff0c;了解到LeGO-LOAM&#xff08;面向復雜情況的輕量級優化地面的雷達里程計&#xff09;&#xff0c;進行了一個學習整理。 Github&#xff1a;https://github.com/RobustFieldAutonomyLab/LeGO-LOAM 論文&#xff1a;https://github.com/Robu…

char data[0]用法總結

struct MyData { int nLen; char data[0]; }; 開始沒有理解紅色部分的內容&#xff0c;上網搜索下&#xff0c;發現用處很大&#xff0c;記錄下來。 在結構中&#xff0c;data是一個數組名&#xff1b;但該數組沒有元素&#xff1b;該數組…

(一)低功耗設計目的與功耗的類型

一、低功耗設計的目的 1.便攜性設備等需求 電子產品在我們生活中扮演了極其重要的作用&#xff0c;便攜性的電子設備便是其中一種。便攜性設備需要電池供電、需要消耗電池的能量。在同等電能提供下&#xff0c;低功耗設計的產品就能夠工作更長的時間。時間的就是生命&#xff…

(轉)徹底學會使用epoll(一)——ET模式實現分析

注&#xff1a;之前寫過兩篇關于epoll實現的文章&#xff0c;但是感覺懂得了實現原理并不一定會使用&#xff0c;所以又決定寫這一系列文章&#xff0c;希望能夠對epoll有比較清楚的認識。是請大家轉載務必注明出處&#xff0c;算是對我勞動成果的一點點尊重吧。另外&#xff0…

MFC的消息映射有什么作用

絕對以下這三個解釋的比較簡潔&#xff0c;特此做個記錄&#xff01;以感謝回答的這些人&#xff01; MFC的消息映射有什么作用: Windows操作系統主要是有消息來處理的&#xff0c;每個程序都有自己的消息隊列&#xff0c;并且這些消息是有優先級的&#xff0c;也就是誰會先…

線性表的鏈式存儲結構

鏈式存儲結構的定義 1.概念定義&#xff1a; - n個結點離散分配 - 彼此通過指針相連 - 每個結點只有一個前驅結點和一個后繼結點 - 首結點沒有前驅結點&#xff0c;尾結點沒有后繼結點 2.專業術語 -首結點&#xff1a;第一個有有效數據的結點 -尾結點&#xff1a;最后一個有有效…

Apache 設置http跳轉至HTTPS訪問

為什么80%的碼農都做不了架構師&#xff1f;>>> <VirtualHost>...</VirtualHost> 中添加如下配置 <IfModule mod_rewrite.c>RewriteEngine onRewriteCond %{SERVER_PORT} 80RewriteRule ^(.*)$ https://域名/$1 [R301,L] </IfModule> 轉…

JAVA線程概念

一、程序與進程 1、程序&#xff1a;一段靜態的代碼。 2、進程&#xff1a;程序的一次動態執行過程&#xff0c;它對應從代碼加載、執行到執行完畢的一個完整過程。 3、進程也稱任務&#xff0c;支持多個進程同時執行的OS就被稱為多進程OS或多任務OS。 二、進程與線程 在一…

(二)功耗的分析

前面學習了進行低功耗的目的個功耗的構成&#xff0c;今天就來分享一下功耗的分析。由于是面向數字IC前端設計的學習&#xff0c;所以這里的功耗分析是基于DC中的power compiler工具&#xff1b;更精確的功耗分析可以采用PT&#xff0c;關于PT的功耗分析可以查閱其他資料&#…

Hibernate創建hqll時報錯

Hibernate 問題,在執行Query session.createQuery(hql) 報錯誤 出錯截圖&#xff1a; 這條語句在java運行環境下&#xff0c;直接連數據庫不出錯&#xff0c;如果在hiberante,struts環境下就出錯 出錯原因&#xff1a;jar包沖突&#xff0c;struts2和hibernate框架中都有antlr包…

.NET Core TDD 前傳: 編寫易于測試的代碼 -- 全局狀態

第1篇: 講述了如何創造"縫". "縫"(seam)是需要知道的概念. 第2篇, 避免在構建對象時寫出不易測試的代碼. 第3篇, 依賴項和迪米特法則. 本文是第4篇, 將介紹全局狀態引起的問題. 全局狀態 全局狀態, 也可以叫做應用程序狀態, 它是一組變量, 這些變量維護著…

(三)系統與架構級低功耗設計

前面講解了使用EDA工具&#xff08;主要是power compiler&#xff09;進行功耗分析的流程&#xff0c;這里我們將介紹在數字IC中進行低功耗設計的方法&#xff0c;同時也結合EDA工具&#xff08;主要是Design Compiler&#xff09;如何實現。我們的講解的低功耗設計主要是自頂向…

python---統計列表中數字出現的次數

1 import collections 2 3 a [1,2,3,1,2,3,4,1,2,5,4,6,7,7,8,9,6,2,23,4,2,1,5,6,7,8,2] 4 b collections.Counter(a) 5 for c in b&#xff1a; print c,b[c] 轉載于:https://www.cnblogs.com/lxs1314/p/7236321.html

MFC入門(一)——MFC是一個編程框架

MFC (Microsoft Foundation Class Library)中的各種類結合起來構成了一個應用程序框架&#xff0c;它的目的就是讓程序員在此基礎上來建立Windows下的應用程序&#xff0c;這是一種相對SDK來說更為簡單的方法。因為總體上&#xff0c;MFC框架定義了應用程序的輪廓&#xff0c;并…

2.數據結構筆記學習--線性表基本操作

線性表的結構定義&#xff1a; 順序表的結構定義&#xff1a; typedef struct {int data[maxSize]; //存放順序表元素的數組&#xff0c;一般用 int A[maxSize];int length; //存放順序表的長度,一般用 int n; }SeqList; 單鏈表結點定義&#xff1a; typedef struct L…

(四)RTL級低功耗設計

前面介紹了系統級的低功耗設計&#xff0c;換句話說就是在系統級降低功耗可以考慮的方面。系統級的低功耗設計&#xff0c;主要是由系統級設計、具有豐富經驗的人員實現&#xff0c;雖然還輪不到我們設計&#xff0c;我們了解一下還是比較好的。我們前端設計人員的重點不在系統…

Unity3D 游戲前端開發技能樹(思維導圖)

如果做游戲也是一種游戲,那么這個游戲的自由度實在是太高了.(導圖源文件鏈接&#xff1a;http://pan.baidu.com/s/1eSHpH5o 密碼&#xff1a;qzl5) 最近要用思維導圖軟件Xmind把自己的思路好好捋一捋,算是溫故知新吧. 轉載于:https://www.cnblogs.com/qiaogaojian/p/6098962.ht…

js forEach

&#xfeff;&#xfeff;forEach()函數從頭到尾把數組遍歷一遍。有三個參數各自是&#xff1a;數組元素。元素的索引&#xff0c;數組本身&#xff08;假設是一個參數就是數組元素&#xff0c;也就是數組的值。var data[1,2,3,4,5,6]; var sum0; data.forEach(function(v){//當…

SQL Server 死鎖的告警監控

原文:SQL Server 死鎖的告警監控今天這篇文章總結一下如何監控SQL Server的死鎖&#xff0c;其實以前寫過MS SQL 監控錯誤日志的告警信息&#xff0c;這篇文章著重介紹如何監控數據庫的死鎖&#xff0c;當然這篇文章不分析死鎖產生的原因、以及如何解決死鎖。死鎖&#xff08;D…

關于web性能一些特性匯總

關于web性能一些特性匯總 DOMContentLoaded & load load事件是window對象上的事件。指的是網頁資源已經加載完畢&#xff08;包括但不限于DOM、圖片、音頻、腳本、插件資源以及CSS&#xff09;。 DOMContentLoaded事件是document對象上的事件。指的是DOM已經加載完畢。IE中…