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，一經查實，立即刪除！