POJ3162 문제 보고서
10784 단어 동적 기획
After every day’s training, flymouse will do a physical examination from which data will obtained and analyzed to help wc’s future training be better instructed. In order to make the results reliable, flymouse is not using data all from N days for analysis. flymouse’s model for analysis requires data from a series of consecutive days during which the difference between the longest and the shortest distances wc walks cannot exceed a bound M. The longer the series is, the more accurate the results are. flymouse wants to know the number of days in such a longest series. Can you do the job for him?
Input The input contains a single test case. The test case starts with a line containing the integers N (N ≤ 106) and M (M < 109). Then follow N − 1 lines, each containing two integers fi and di (i = 1, 2, …, N − 1), meaning the check-points i + 1 and fi are connected by a path of length di.
Output Output one line with only the desired number of days in the longest series.
Sample Input 3 2 1 1 1 3 Sample Output 3 Hint Explanation for the sample:
There are three check-points. Two paths of lengths 1 and 3 connect check-points 2 and 3 to check-point 1. The three paths along with wc walks are 1-3, 2-1-3 and 3-1-2. And their lengths are 3, 4 and 4. Therefore data from all three days can be used for analysis.
제목: 나무 한 그루를 드리겠습니다. 직접 연결된 두 노드의 가장자리에 권한이 있습니다. 하나, 둘, 셋, 넷..., n개의 노드의 가장 긴 거리를 구하세요.d[1],d[2],…,d[n]; 그리고 최대 r-l를 찾아서 이 [l,r] 구간의 최대 값을 최소 값으로
//
// Created by Running Photon on 2015-09-08
// Copyright (c) 2015 Running Photon. All rights reserved.
//
//
//#pragma comment(linker, "/STACK:102400000,102400000")
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define ALL(x) x.begin(), x.end()
#define INS(x) inserter(x, x,begin())
#define ll long long
#define CLR(x) memset(x, 0, sizeof x)
#define MAXN 9999
#define MAXSIZE 10
#define DLEN 4
using namespace std;
const int inf = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
const int maxn = 2e6 + 10;
const int maxv = 1e6 + 10;
const double eps = 1e-9;
inline int read() {
char c = getchar();
int f = 1;
while(!isdigit(c)) {
if(c == '-') f = -1;
c = getchar();
}
int x = 0;
while(isdigit(c)) {
x = x * 10 + c - '0';
c = getchar();
}
return x * f;
}
int n, k;
int head[maxv], pnt[maxn], cnt, nxt[maxn], cost[maxn];
int dis[maxv], root1, root2, d[maxv];
void add_edge(int u, int v, int val) {
pnt[cnt] = v;
cost[cnt] = val;
nxt[cnt] = head[u];
head[u] = cnt++;
}
void findRoot(int u, int fa, int &root) {
for(int i = head[u]; ~i; i = nxt[i]) {
int v = pnt[i];
if(v == fa) continue;
dis[v] = dis[u] + cost[i];
findRoot(v, u, root);
}
if(dis[u] > dis[root]) {
root = u;
}
d[u] = max(d[u], dis[u]);//dfs d
}
void work() {
root1 = 1, root2 = 1;
findRoot(1, 1, root1);// 1
dis[root1] = 0;
findRoot(root1, root1, root2); 2
dis[root2] = 0;
findRoot(root2, root2, root1);// 2 dfs
}
void sol() {
int ans = 0;
deque <int> dequemax, dequemin;
int l = 1, r = 1;
for(; r <= n; r++) {
while(dequemax.size() && d[r] >= d[dequemax.back()]) {
dequemax.pop_back();
}
dequemax.push_back(r);
while(dequemin.size() && d[r] <= d[dequemin.back()]) {
dequemin.pop_back();
}
dequemin.push_back(r);
if(d[dequemax[0]] - d[dequemin[0]] > k) {
while(d[dequemax[0]] - d[dequemin[0]] > k) {
l = min(dequemax[0], dequemin[0]) + 1;
while(dequemax[0] < l) dequemax.pop_front();
while(dequemin[0] < l) dequemin.pop_front();
}
ans = max(ans, r - l + 1);
}
ans = max(ans, r - l + 1);
}
printf("%d
", ans);
}
int main() {
#ifdef LOCAL
freopen("in.txt", "r", stdin);
// freopen("out.txt","w",stdout);
#endif
while(scanf("%d%d", &n, &k) != EOF) {
cnt = 0;
CLR(d);
memset(head, -1, sizeof head);
for(int i = 2; i <= n; i++) {
int u = read(), val = read();
add_edge(i, u, val);
add_edge(u, i, val);
}
work();
sol();
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
01 가방, 완전 가방, 다중 가방 dp(동적 기획 입문 dp)01 가방은 2진법으로 직접 표시할 수 있지만 데이터 양이 너무 많으면 시간을 초과하는 것이 폭력이다.01 가방의 사상은 바로 이 물품에 대해 내가 넣은 가치가 큰지 안 넣은 가치가 큰지 비교하여 방정식 f[i][v...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.