C++博客-糯米-最新评论

re: Minimal Steiner Tree 简介

EUYUIL — Sat, 11 Feb 2012 08:24:00 GMT

博主，假设有一张图，是完全二叉树的情况，有 8 个叶子节点，这样内点是 7 个啊，为什么说是 N - 2 呢？盼解答。

EUYUIL 2012-02-11 16:24 发表评论

re: POJ 2374 Fence Obstacle Course 线段树+动态规划

CWQBUPT — Sat, 28 Jan 2012 17:28:00 GMT

知道为什么要用线段树，我直接开辟一个数组，每次将第i个fense的区间标记为i，好像也能得到正确的结果，可是会运行超时，不知道为什么？
#include "stdafx.h"
#include

#define MAX_N 50032
#define MAX_R 100032

struct {
int a, b;
} dp[MAX_N], fences[MAX_N];
int N, S;

int seg[MAX_R*2];

__inline int max(int a, int b)
{
return a > b ? a : b;
}

__inline int abs(int a)
{
return a > 0 ? a : -a;
}

__inline int min(int a, int b)
{
return a < b ? a : b;
}

__inline int calc_min(int i, int pos)
{
if (!i)
return abs(pos - MAX_R);
return min(pos - fences[i].a + dp[i].a, fences[i].b - pos + dp[i].b);
}

int main()
{
//for(int k=0;k //{
// seg[k] = 0;
//}

int i;

freopen("e:\\test\\in.txt", "r", stdin);

scanf("%d%d", &N, &S);
S += MAX_R;
for (i = 1; i <= N; i++) {
scanf("%d%d", &fences[i].a, &fences[i].b);
fences[i].a += MAX_R;
fences[i].b += MAX_R;
dp[i].a = calc_min( seg[ fences[i].a ], fences[i].a);
dp[i].b = calc_min( seg[ fences[i].b ], fences[i].b);

for (int j=fences[i].a;j<=fences[i].b;++j)
{
seg[j] = i;
}

}
printf( "%d\n",
min(S - fences[N].a + dp[N].a, fences[N].b - S + dp[N].b)
);

return 0;
}

CWQBUPT 2012-01-29 01:28 发表评论