[POI1999]遗传密码

成绩 0 开启时间 2013年01月16日 星期三 06:50
折扣 0.8 折扣时间 2013年01月16日 星期三 06:50
允许迟交 关闭时间 2013年01月16日 星期三 06:50
输入文件 pie.in 输出文件 pie.out

问题描述

一个 primitivus 的 遗传密码 是一串自然数 K= ( a_1,...,a_n ) 。所有在 primitivus 的遗传密码中连续出现的数对 ( l , r ) 被称为一个 primitivus 的 特征 。例如存在一个 i , l=a[i], r=a[i+1] 。在 primitivus 的遗传密码中没有形如 ( p , p ) 的特征。 任务

写一个程序

  • 从输入文件中读入特征的列表
  • 计算 primitivus 的遗传密码的最短长度
  • 将结果写到输出文件

输入格式

在输入文件的第一行有一个正整数 n ,表示 primitivus 的遗传密码的不同的特征。在接下来的 n 行中,每行有一对自然数 l 和 r ,用空格隔开, 1 <= l <= 1000, 1 <= r <= 1000 。数对 ( l , r ) 是 primitivus 的特征。特征不会在输入文件中重复出现。

输出格式

你的程序应当向输出文件输出一个数,表示包含输入文件中所有特征的最短的 primitivus 遗传密码的长度。

输入样例

12
2 3
3 9
9 6
8 5
5 7
7 6
4 5
5 1
1 4
4 2
2 8
8 6 

输出样例

15

注释

下面的遗传密码包含了所有特征:

(8, 5, 1, 4, 2, 3, 9, 6, 4, 5, 7, 6, 2, 8, 6)