oyjpArt ACM/ICPC算法程序设计空间

// I am new in programming, welcome to my blog
I am oyjpart(alpc12, 四城)
posts - 224, comments - 694, trackbacks - 0, articles - 6
Minimizing maximizer
Time Limit: 5000MS Memory Limit: 30000K
Total Submissions: 1004 Accepted: 280

Description
The company Chris Ltd. is preparing a new sorting hardware called Maximizer. Maximizer has n inputs numbered from 1 to n. Each input represents one integer. Maximizer has one output which represents the maximum value present on Maximizer's inputs.

Maximizer is implemented as a pipeline of sorters Sorter(i1, j1), ... , Sorter(ik, jk). Each sorter has n inputs and n outputs. Sorter(i, j) sorts values on inputs i, i+1,... , j in non-decreasing order and lets the other inputs pass through unchanged. The n-th output of the last sorter is the output of the Maximizer.

An intern (a former ACM contestant) observed that some sorters could be excluded from the pipeline and Maximizer would still produce the correct result. What is the length of the shortest subsequence of the given sequence of sorters in the pipeline still producing correct results for all possible combinations of input values?

Task
Write a program that:

reads a description of a Maximizer, i.e. the initial sequence of sorters in the pipeline,
computes the length of the shortest subsequence of the initial sequence of sorters still producing correct results for all possible input data,
writes the result.

Input
The first line of the input contains two integers n and m (2 <= n <= 50000, 1 <= m <= 500000) separated by a single space. Integer n is the number of inputs and integer m is the number of sorters in the pipeline. The initial sequence of sorters is described in the next m lines. The k-th of these lines contains the parameters of the k-th sorter: two integers ik and jk (1 <= ik < jk <= n) separated by a single space.

Output
The output consists of only one line containing an integer equal to the length of the shortest subsequence of the initial sequence of sorters still producing correct results for all possible data.

Sample Input

40 6
20 30
1 10
10 20
20 30
15 25
30 40

 

Sample Output

4

 

Hint
Huge input data, scanf is recommended.

Source
Central Europe 2003

//pku1769
/*
 * trival DP dp[i] = dp[j] + 1 (if there is a segment starting from a->i && a <= j)  o(n^2)
 * 考虑到转移的时候选择的是一段内的最小dp值,运用点树可以解决
 */
#include <string.h>
#include <stdio.h>

const int N = 50010;
const int MAXINT = 1000000000;

int n, l;

struct ST {int i,j,m,l,r,c;} st[2*N];
int up, cnt;

void bd(int d, int x, int y) {
 st[d].i = x, st[d].j = y, st[d].m = (x+y)/2, st[d].c = MAXINT;
 if(x < y) {
  st[d].l = ++up; bd(up, x, st[d].m);
  st[d].r = ++up; bd(up, st[d].m+1, y);
 }
}

void ins(int d, int x, int c) {
 if(c < st[d].c)
  st[d].c = c;
 if(st[d].i != st[d].j) {
  if(x <= st[d].m)
   ins(st[d].l, x, c);
  else
   ins(st[d].r, x, c);
 }
}

int getmin(int d, int x, int y) {
 if(x <= st[d].i && y >= st[d].j)
  return st[d].c;
 int min = MAXINT;
 if(x <= st[d].m) {
  int now = getmin(st[d].l, x, y);
  if(now < min) min = now;
 }
 if(y > st[d].m) {
  int now = getmin(st[d].r, x, y);
  if(now < min) min = now;
 }
 return min;
}

int main() {
 int i, a, b;
 up = 0;
 scanf("%d %d ", &l, &n);
 bd(0, 1, l);
 ins(0, 1, 0);
 int max = 0;
 for(i = 0; i < n; ++i) {
  scanf("%d%d", &a, &b);
  if(a < b) {
   int min = getmin(0, a, b-1);
   ins(0, b, min+1);
  }
 }
 printf("%d\n", getmin(0, l, l));
 return 0;
}

Feedback

# re: pku1769 新写的线段树(点树)模版  回复  更多评论   

2007-12-04 16:33 by je
题目没看懂,能解释下么?

# re: pku1769 新写的线段树(点树)模版  回复  更多评论   

2007-12-05 11:47 by oyjpart
给定一个线段集,要求选择其中一个最小的子集来覆盖整个区域。
要求选定的子集是按照题目给的序来覆盖。

# re: pku1769 新写的线段树(点树)模版  回复  更多评论   

2008-01-18 08:46 by Littleye
很多测试好像得不到正确答案,例如:
40 4
10 30
14 29
25 30
30 40
答案应该是2,你的程序给的是1000000000(你的初始值)
类似的例子还有不少

# re: pku1769 新写的线段树(点树)模版  回复  更多评论   

2008-01-18 12:40 by oyjpart
你的样例是无解的,没有线段覆盖【0,10】的区间。

# re: pku1769 新写的线段树(点树)模版  回复  更多评论   

2008-01-19 02:33 by Littleye
I understand now. I don't think I understood the problem thoroughly before. Although the problem description doesn't clearly indicate that all the segments given should cover the whole segment(1,N), it is the right situation or else we can't get the right output from the maximizer. Now the problem description says that we can get the right output, so the subsequences given must cover the whole segments. Thanks a lot!

# re: pku1769 新写的线段树(点树)模版  回复  更多评论   

2008-01-19 12:34 by oyjpart
you are welcome

# re: pku1769 新写的线段树(点树)模版  回复  更多评论   

2008-04-18 10:44 by l-y-p
向大牛学习学习,“运用点树可以解决”,好思想,很好很强大。但是还有一个疑点:在DP的时候应该从小到大进行,但是没发现你对y坐标进行排序就直接进行,那如果是考虑这样两组数据:
10 40
0 10
从10到40先确定到40的DP值为maxint+1,然后再由0~10确定10的值为1,这样是不是有问题??你的程序我没调试过,不晓得你是怎么处理的?

# re: pku1769 新写的线段树(点树)模版  回复  更多评论   

2008-04-18 10:58 by l-y-p
果然啊,刚调试了下,直接运行数据:
40 2
10 40
0 10
结果是1000000000,不知道是我没看清楚还是程序的bug?

# re: pku1769 新写的线段树(点树)模版  回复  更多评论   

2008-04-18 12:19 by oyjpart
题目是有这样的要求的:
要求选定的子集是按照题目给的序来覆盖。
嘿嘿 如果我没有理解错你的意思的话

# re: pku1769 新写的线段树(点树)模版  回复  更多评论   

2008-04-18 22:02 by l-y-p
汗!
What is the length of the shortest subsequence of the given sequence of sorters
把排序一去掉就AC了,多谢大牛指点,呵呵。
最先还一直在想如果可以排序的话就用不着用点树了,直接贪心!

# re: pku1769 新写的线段树(点树)模版  回复  更多评论   

2009-08-25 10:39 by demo
你的程序过不了zoj 2451

# re: pku1769 新写的线段树(点树)模版  回复  更多评论   

2009-09-07 23:58 by oyjpart
题目是一样的吗

# re: pku1769 新写的线段树(点树)模版  回复  更多评论   

2010-12-01 20:36 by LSK
请仔细读题。。。ZJU哪个是multi case的

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理