歌曲：时光倒流
歌手：汪峰 专辑：怒放的生命
那天傍晚我走在街边看着往来如浪的人群
想起曾经走过的岁月想起曾经热爱的你
我没有该去的地方也不知道身处何处
只因为你已不在这里这思念让我心动
我想哭却流不出眼泪
我相喊却发不出声音
我愿意抛弃我的所有
如果能时光倒流
夕阳洒在我的脸上风儿拔动我的心弦
我多想你就坐在我的身旁
没有你我有多孤独
我想哭却流不出眼泪
我想喊却发不出声音
我愿意抛弃我的所有
如果能时光倒流
我想哭却流不出眼泪
我想喊却发不出声音
我愿意抛弃我的所有
如果能时光倒流
如果能时光倒流
如果能时光倒流
先枚举预处理每两个单词之间的最大值。
然后易看出是寻找遍历所有顶点一遍的最长路径。
状态 d[1<<10][10]，d[i][j] 代表用了哪 i 个顶点，最后一个顶点为 j 的最长路经。
递推方程 (0=<i<(1<<n), 0=<j, k<n)
if ( vertex k no used )
d[i+(1<<k)][k]=max( d[i+(1<<k)][k], d[i][j]+maxsub[j][k] );
初始化 d[1<<i][i] = 0; (0 <= i < n)
Saratov State University 2006 World Champions
Rank Name Solved Time
1 Saratov State University 6 917
2 Jagiellonian University - Krakow 6 1258
3 Altai State Technical University 5 681
4 University of Twente 5 744
5 Shanghai Jiao Tong University 5 766
6 St. Petersburg State University 5 815
7 Warsaw University 5 820
8 Massachusetts Institute of Technology 5 831
9 Moscow State University 5 870
10 Ufa State Technical University of Aviation 5 980
11 University of Alberta 4 479
12 University of Waterloo 4 636
13 Instituto Tecnologico de Aeronautica 4
13 Korea Advanced Institute of Science and Technology 4
13 Peking University 4
13 Sharif University of Technology 4
13 University of British Columbia 4
13 Zhejiang University 4
19 Information & Communications University 3
19 KTH - Royal Institute of Technology 3
19 Kyoto University 3
19 Lund University 3
19 National Taiwan University 3
19 Petrozavodsk State University 3
19 Pontifícia Universidade Católica do Rio de Janeiro 3
19 Seoul National University 3
19 Simon Fraser University 3
19 Sofia University 3
19 South Ural State University 3
19 St Petersburg Institute of Fine Mechanics & Optics 3
19 Taras Shevchenko Kyiv University 3
19 Technische Universit?t München 3
19 The University of Hong Kong 3
19 Tsinghua University 3
19 University of Science and Technology of China 3
19 University of Tokyo 3
19 University of Toronto 3
19 Zhongshan (Sun Yat-sen) University 3
39 Bangladesh University of Engineering & Technology 2
39 California Institute of Technology 2
39 DePaul University 2
39 Fudan University 2
39 Fuzhou University 2
39 Princeton University 2
39 Renmin University of China 2
39 The Chinese University of Hong Kong 2
39 Universidad Nacional de Colombia 2
39 Universitat Politècnica de Catalunya 2
39 University of Adelaide 2
39 University of Cape Town 2
39 University of Maryland - College Park 2
39 Vinnytsia National Technical University 2
39 Washington University in St. Louis 2
39 Yaroslavl Demidov State University 2
39 école Nationale Supérieure des Télécom Paris 2
Honorable Mention
Ateneo de Manila University Sichuan University
Binghamton University South Dakota School of Mines & Technology
Cairo University - Faculty of Computers & Information Stony Brook University
Carnegie Mellon University The American University in Cairo
Duke University Universidad Aut贸noma de Tlaxcala
Facultad de Matematica, Astronomia y Fisica - UNC Universidad Central de Venezuela
Georgia Institute of Technology Universidad Tecnol贸gica de la Mixteca
Ho Chi Minh City University of Technology University of Auckland
Indian Institute of Information Technology, Allahabad University of Central Florida
Indian Institute of Technology Bombay University of Dhaka
Kazakh-British Technical University University of Nebraska - Lincoln
Madras Institute of Technology University of Wisconsin - Madison
Rice University Ural State University
Shahid Beheshti University Virginia Tech
Region Champion
Africa and the Middle East University of Cape Town
Asia Shanghai Jiao Tong University
Europe Saratov State University
Latin America Instituto Tecnologico de Aeronautica
North America Massachusetts Institute of Technology
South Pacific University of Adelaide
bellman-ford在差分约束中的应用。
设S(i)为 1..i 中在最终序列中的的整数个数。
则易得到
S(b) - S(a) >= c
0 <= S(i) - S(i-1) <= 1
—>
S(i) - S(i-1) >= 0
S(i-1) - S(i) >= -1
得到了约束条件。bellman-ford搞掉。
去年暑假第一次听说差分约束和bellman-ford都是lrm给介绍的，后来看了算法导论也没有写过。
在weborad偶然发现此题，经lrm提醒后ac。
看了roba的blog，还有2个题目，先放在这里，以后搞掉。
TOJ 1239 Cashier Employment
HOJ 2168 Working with Relations
