Jingjing the panda lives in a forest containing n
pieces
of bamboo land. Each bamboo land is very small and can be regarded as a single
point. Bamboo land i
contains Li
bamboos and is associated with a ``deliciousness'' Wi
.
Jingjing eats all
bamboos in a selected bamboo land every day. He has a bad habit: the
deliciousness of the bamboo land he selects must be strictly larger than that
of the day before.
Moving from one
land to another is very tiring. The longer Jingjing walks before arriving a
bamboo land i
, the more bamboo he is expecting. If the distance he
walked from the last bamboo land is strictly larger than the number of bamboos
he finds in the current land (i.e Li
), he will die of sadness.
Distance of two
points (x0, y0)
and (x1, y1)
equals to
| x0 - x1| + | y0 - y1|
, since Jingjing only moves north, south,
east and west.
When you send
Jingjing in one bamboo land someday, how many days can Jingjing survive (Jingjing
is clever enough to find out the optimal way of living)?
We need this
information so that we can bring him out before he dies.
The first line contains a single integer t
(
1
t10
), the
number of test cases. Each test case contains several lines.
The first line contains a single integer n
(
1n100, 000
), the
number of bamboo lands. The next n lines each contains 4
integers Xi
, Yi
, Wi
,Li
,
indicating the coordinate of i
-th bamboo land, its deliciousness and number of bamboos.
You may assume that
0Xi, Yi, Wi, Li1, 000, 000
. No two lands have the same deliciousness. Two bamboo lands can
be so close that they can be regarded as at the same point.
For each test
case, print the case number followed by the number of days Jingjing can
survive. Look at the output for sample input for details.
2
3
0 0 3 4
2 2 2 3
5 5 1 3
3
0 0 3 4
2 2 2 3
5 5 1 3
Case 1: 2
Case 2: 2
TLE Version by only DP
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;
struct E {
int x, y, w, l;
E(int a=0, int b=0, int c=0, int d=0) {
x = a, y = b;
w = c, l = d;
}
bool operator<(const E &a) const {
return w > a.w;
}
};
E D[100005];
int main() {
/*freopen("in.txt","r+t",stdin);
freopen("out2.txt","w+t",stdout);*/
int testcase, cases = 0;
int a, b, c, d;
int x, y;
int i, j, k;
int n;
scanf("%d", &testcase);
while(testcase--) {
scanf("%d", &n);
for(i = 0; i < n; i++) {
scanf("%d %d %d %d", &a, &b, &c, &d);
D[i] = E(a, b, c, d);
}
sort(D, D+n);
int dp[100005] = {};
for(i = 0; i < n; i++) {
for(j = i+1; j < n; j++) {
if(abs(D[i].x-D[j].x)+abs(D[i].y-D[j].y) <= D[i].l)
dp[j] = max(dp[j], dp[i]+1);
}
//printf("%d %d\n", dp[i]+1, D[i].w);
}
int ret = 0;
for(i = 0; i < n; i++)
ret = max(ret, dp[i]);
printf("Case %d: %d\n", ++cases, ret+1);
}
return 0;
}
題目描述： 熊貓吃竹子，2D 整數點座標有數處竹林，每處竹林有蘊藏量和美味度，熊貓每次都會往美味度更高的地方走，如果下一個點距離高於該地蘊藏量時，這隻熊貓會在抵達後傷心而死。
求熊貓會多能活幾天(每天只吃一處竹林)。
題目解法：
很明顯地察覺到這是一題 DP 問題，但是共有 100000 處竹林，其餘數值都在 [0,1000000]。
方格法感覺也不對，由於計算距離是曼哈頓距離，因此感覺可以使用旋轉 45 度後，
掛上可變調的二維線段樹， 講到這裡不經寒顫一番。
因此這裡寫一個"專門"寫這題的四分樹，支持區域極值更新。
旋轉時，特別注意：
在負數索引值二分時，特別注意， 由於 mid = (l+r)/2 的取整 ...
由於旋轉後會有負數可能，四分樹遞迴切割計算上會有問題！
由於數據離散，建造四分樹採用插入節點的方式，因此會存在深度很深的孤枝，多寫一個 reduce() 壓縮長度。
快了 200 ms。
#include <stdio.h>
#include <string.h>
#include <queue>
#include <algorithm>
using namespace std;
struct QuadTreeNode {
int lx, ly, rx, ry;//[lx, rx]x[ly, ry]
int v, label;
QuadTreeNode *s1, *s2, *s3, *s4;
QuadTreeNode(int a, int b, int c, int d) {
lx = a, ly = b, rx = c, ry = d;
v = label = 0;
s1 = s2 = s3 = s4 = NULL;
}
};
struct QuadTree {// maximum value(non negtive value) record.
QuadTreeNode *root;
QuadTree(int lx, int ly, int rx, int ry) {
root = new QuadTreeNode(lx, ly, rx, ry);
}//s1 [lx,mx]x[ly,my], s2 [lx,mx]x[my+1,ry], s3 [mx+1,ry]x[ly,my]
void updateLabel(QuadTreeNode *node) {
if(node->s1) node->s1->label = max(node->s1->label, node->label);
if(node->s2) node->s2->label = max(node->s2->label, node->label);
if(node->s3) node->s3->label = max(node->s3->label, node->label);
if(node->s4) node->s4->label = max(node->s4->label, node->label);
node->v = max(node->v, node->label);
node->label = 0;
}
void modify(QuadTreeNode *node, int lx, int ly, int rx, int ry, int v) {
if(node == NULL) return;
if(node->rx < lx || node->lx > rx || node->ry < ly || node->ly > ry)
return;
if(lx <= node->lx && node->rx <= rx && ly <= node->ly && node->ry <= ry) {
node->label = max(node->label, v);
return;
}
modify(node->s1, lx, ly, rx, ry, v);
modify(node->s2, lx, ly, rx, ry, v);
modify(node->s3, lx, ly, rx, ry, v);
modify(node->s4, lx, ly, rx, ry, v);
}
int query(QuadTreeNode *node, int lx, int ly, int rx, int ry) {
if(node == NULL) return 0;
if(node->rx < lx || node->lx > rx || node->ry < ly || node->ly > ry)
return 0;
if(node->label)
updateLabel(node);
if(lx <= node->lx && node->rx <= rx && ly <= node->ly && node->ry <= ry)
return node->v;
int ret = 0;
ret = max(ret, query(node->s1, lx, ly, rx, ry));
ret = max(ret, query(node->s2, lx, ly, rx, ry));
ret = max(ret, query(node->s3, lx, ly, rx, ry));
ret = max(ret, query(node->s4, lx, ly, rx, ry));
return ret;
}
void insert(int x, int y) {// init build tree data point
QuadTreeNode *node, *next;
node = root;
while(true) {
if(node->lx == node->rx && node->ly == node->ry) {
if(node->lx == x && node->ly == y)
break;
}
int mx, my;
mx = (node->lx + node->rx)/2, my = (node->ly + node->ry)/2;
if(x <= mx) {
if(y <= my) {//s1
if(node->s1 == NULL)
node->s1 = new QuadTreeNode(node->lx, node->ly, mx, my);
next = node->s1;
} else {//s2
if(node->s2 == NULL)
node->s2 = new QuadTreeNode(node->lx, my+1, mx, node->ry);
next = node->s2;
}
} else {
if(y <= my) {//s3
if(node->s3 == NULL)
node->s3 = new QuadTreeNode(mx+1, node->ly, node->rx, my);
next = node->s3;
} else {//s4
if(node->s4 == NULL)
node->s4 = new QuadTreeNode(mx+1, my+1, node->rx, node->ry);
next = node->s4;
}
}
node = next;
}
}
QuadTreeNode* reduce(QuadTreeNode *node, QuadTreeNode *p, int s) {// after call reduce(), could not call insert()
if(node == NULL) return NULL;
int cnt = 0;
QuadTreeNode *pt, *t;
t = reduce(node->s1, node, 1);
if(t) pt = t, cnt++;
t = reduce(node->s2, node, 2);
if(t) pt = t, cnt++;
t = reduce(node->s3, node, 3);
if(t) pt = t, cnt++;
t = reduce(node->s4, node, 4);
if(t) pt = t, cnt++;
if(cnt == 1) {
delete node;
if(p != NULL) {
if(s == 1) p->s1 = pt;
if(s == 2) p->s2 = pt;
if(s == 3) p->s3 = pt;
if(s == 4) p->s4 = pt;
}
return pt;
}
return node;
}
void freeTree() {
queue<QuadTreeNode*> Q;
QuadTreeNode *node;
Q.push(root);
while(!Q.empty()) {
node = Q.front(), Q.pop();
if(node->s1) Q.push(node->s1);
if(node->s2) Q.push(node->s2);
if(node->s3) Q.push(node->s3);
if(node->s4) Q.push(node->s4);
delete node;
}
}
};
struct E {
int x, y, w, l;
E(int a=0, int b=0, int c=0, int d=0) {
x = a-b, y = a+b;
w = c, l = d;
}
bool operator<(const E &a) const {
return w > a.w;
}
};
E D[100005];
int main() {
/*freopen("in.txt","r+t",stdin);
freopen("out.txt","w+t",stdout);*/
int testcase, cases = 0;
int a, b, c, d;
int x, y;
int i, j, k;
int n;
scanf("%d", &testcase);
while(testcase--) {
scanf("%d", &n);
for(i = 0; i < n; i++) {
scanf("%d %d %d %d", &a, &b, &c, &d);
D[i] = E(a, b, c, d);
}
#define oo 0xfffffff
int lx = oo, ly = oo, rx = -oo, ry = -oo;
int bx, by;//base_x, base_y
for(i = 0; i < n; i++) {
lx = min(lx, D[i].x), ly = min(ly, D[i].y);
rx = max(rx, D[i].x), ry = max(ry, D[i].y);
}
bx = lx, by = ly;
lx -= bx, rx -= bx, ly -= by, ry -= by;
sort(D, D+n);
QuadTree QT(lx, ly, rx, ry);
for(i = 0; i < n; i++) {
D[i].x -= bx, D[i].y -= by;
QT.insert(D[i].x, D[i].y);
}
QT.reduce(QT.root, NULL, 0);
int ret = 0;
for(i = 0; i < n; i++) {
int val = QT.query(QT.root, D[i].x, D[i].y, D[i].x, D[i].y)+1;
int cx = D[i].x, cy = D[i].y, l = D[i].l;
QT.modify(QT.root, cx-l, cy-l, cx+l, cy+l, val);
ret = max(ret, val);
}
printf("Case %d: %d\n", ++cases, ret);
QT.freeTree();
}
return 0;
}
文章定位：
