|
|
樹的直徑是指樹的最長簡單路。求法: 兩遍BFS :先任選一個(gè)起點(diǎn)BFS找到最長路的終點(diǎn)，再從終點(diǎn)進(jìn)行BFS，則第二次BFS找到的最長路即為樹的直徑； 原理: 設(shè)起點(diǎn)為u,第一次BFS找到的終點(diǎn)v一定是樹的直徑的一個(gè)端點(diǎn) 證明: 1) 如果u 是直徑上的點(diǎn)，則v顯然是直徑的終點(diǎn)(因?yàn)槿绻鹶不是的話，則必定存在另一個(gè)點(diǎn)w使得u到w的距離更長，則于BFS找到了v矛盾) 2) 如果u不是直徑上的點(diǎn)，則u到v必然于樹的直徑相交(反證),那么交點(diǎn)到v 必然就是直徑的后半段了 所以v一定是直徑的一個(gè)端點(diǎn)，所以從v進(jìn)行BFS得到的一定是直徑長度 相關(guān)題目有TOJ1056，TOJ3517. TOJ 1056(Labyrinth): 大意是一個(gè)由‘#’和'.'構(gòu)成的迷宮，'.'表示可行，‘#’表示不可行，問可行的最長的路的長度是多少。
#include <cstdio>
#include <cstring>
#include <queue>
#define M 1002
using namespace std;
int r,c;
char map[M][M];
bool flag[M][M];
int move[4][2]={-1,0,1,0,0,-1,0,1}; // 分別表示上下左右
int maxt;
struct Node{
int x,y,num;
};
Node ans;
bool legal(int x,int y){ //判斷該點(diǎn)是否越界及是否可走
if(x >=0 && x < r && y>=0 && y < c &&map[x][y]=='.') return true;
return false;
}
void bfs(Node start){
memset(flag,false,sizeof(flag)); //初始所有點(diǎn)標(biāo)記為false
flag[start.x][start.y] = true; //起點(diǎn)標(biāo)記為true
queue<Node>f;
while(!f.empty()) f.pop(); //清空創(chuàng)建的隊(duì)列
Node m,n,tep;
int tx,ty,xx,yy;
int i,j,k,num;
f.push(start);
while(!f.empty()){ //如果隊(duì)列不為空
m = f.front(); //取出隊(duì)首元素
tx = m.x; ty = m.y; num = m.num;
if(num > maxt){ //如果該元素的長度大于maxt，更新maxt
maxt = num;
ans = m;
}
for(i = 0;i < 4; i++){ //以m為起點(diǎn)向4個(gè)方向BFS
xx = tx + move[i][0];
yy = ty + move[i][1];
if(!flag[xx][yy] && legal(xx,yy)){
flag[xx][yy] = true;
tep.x = xx;
tep.y = yy;
tep.num = num + 1;
f.push(tep);
if(num+1>maxt){ //如果有更大的則更新
maxt = num + 1;
ans = tep;
}
}
}
f.pop(); //彈出隊(duì)首元素
}
}
int main(){
int i,j,T;
Node start,end;
bool mark;
scanf("%d",&T);
while(T--){
scanf("%d%d",&c,&r);
mark = false; maxt = -1;
for(i = 0;i < r; i++)
scanf("%s",map[i]);
for(i = 0;i < r; i++){
for(j = 0;j < c; j++){
if(map[i][j]=='.'){ //任選一點(diǎn)BFS
start.x = i;
start.y = j;
start.num = 0;
bfs(start);
mark = true;
break;
}
}
if(mark) break;
}
maxt = -1;ans.num = 0; //此時(shí)ans一定是直徑的端點(diǎn)，將它設(shè)為起點(diǎn)
bfs(ans); //進(jìn)行第二次BFS
printf("Maximum rope length is %d.\n",maxt);
}
}
TOJ3517(The longest athletic track): 題目給出了一棵生成樹，問這棵生成樹最長的路的長度是多少。
#include<iostream>
#include<queue>
#define INF 999999
#define M 2002
using namespace std;
int n;
int maxx;
int map[M][M],sum[M];
bool flag[M];
int bfs(int begin){
queue<int>f;
int i,m,k,key;
maxx=0;
memset(flag,false,sizeof(flag));
f.push(begin);
while(!f.empty()){
k=f.front();
for(i=1;i<=n;i++){
if(map[k][i]!=INF&&!flag[i]){
flag[i]=true;
f.push(i);
sum[i]=sum[k]+map[k][i];
if(sum[i]>maxx) { maxx=sum[i];key=i; }
}
}
f.pop();
}
return key;
}
int main()
{
int i,j,k,dis,key,cas;
scanf("%d",&cas);
while(cas--){
scanf("%d",&n);
for(i=1;i<n;i++)
for(j=i+1;j<=n;j++)
map[i][j]=map[j][i]=INF;
for(i=1;i<n;i++){
scanf("%d%d%d",&j,&k,&dis);
map[j][k]=map[k][j]=dis;
}
sum[1]=0;
key=bfs(1);
sum[key]=0;
key=bfs(key);
printf("%d\n",maxx);
}
//system("pause");
}
早就想學(xué)一下歸并排序求逆序?qū)Γ谶@之前只會(huì)用樹狀數(shù)組來做，有時(shí)候還需要離散化，而且效率還不如歸并排序高。 其實(shí)還是蠻簡單的，知道歸并排序的原理就很容易知道如何求逆序?qū)α恕ＴO(shè)數(shù)組為A，關(guān)鍵是在合并的時(shí)候，用數(shù)組L 和 R 表示左右兩個(gè)子數(shù)組，因?yàn)槟嫘驅(qū)Φ膫€(gè)數(shù)f(A) = f(L) + f(R) + s(L,R);其中f(L) 和 f(R) 分別表示L 內(nèi)部 和R內(nèi)部的逆序?qū)€(gè)數(shù)，s(L.R)表示大數(shù)在L，小數(shù)在R的逆序?qū)ΑＲ驗(yàn)長和R是已經(jīng)排好序的，故其實(shí)只需求s(L,R).這個(gè)可以在合并L和R依次進(jìn)行比較的時(shí)候算出。
for(k = p;k <= r;k ++){
if(L[i]<=R[j])
a[k] = L[i++];
else{ //如果L最上面的數(shù)大于R的，那么L[i]及后面的數(shù)可以和R[j]構(gòu)成n1-i+1個(gè)逆序?qū)?br> a[k] = R[j++];
count +=(n1 -i + 1); //累加
}
}
歸并排序的代碼：
void merge(int p,int q,int r){
int n1 = q-p+1,n2 = r-q;
int i,j,k;
for(i = 1;i <= n1; i++)
L[i] = a[p+i-1];
for(j = 1;j <= n2; j++)
R[j] = a[q+j];
L[n1+1] = INF;
R[n2+1] = INF;
i = 1;j = 1;
for(k = p;k <= r;k ++){
if(L[i]<=R[j])
a[k] = L[i++];
else{
a[k] = R[j++];
count +=(n1 -i + 1);
}
}
}
void merge_sort(int p,int r){
if(p<r){
int q = (p+r)/2;
merge_sort(p,q);
merge_sort(q+1,r);
merge(p,q,r);
}
}
今天看了下多重背包，理解的還不夠深入，不過因?yàn)槭?1背包過來的，所以接受起來很容易。 主要是運(yùn)用了二進(jìn)制的思想將一個(gè)數(shù)量為N很大的物品分為了logN個(gè)數(shù)量小的物品，而這logN個(gè)物品可以組成數(shù)量為0到N任意數(shù)量，所以這種策略是 成立的。 多重背包問題有TOJ1034，TOJ1670. TOJ1034 : 大意是有6種規(guī)格的石頭，編號從1到6，編號為 i 的石頭的價(jià)值為 i .現(xiàn)在給出各種石頭的數(shù)量，問有沒有可能得到總價(jià)值的一半。 做法: DP, 每種石頭價(jià)值為v[i],價(jià)值為 i ，數(shù)量為 num[i] ,通過多重背包看能不能恰好取得總價(jià)值的一半。 一個(gè)優(yōu)化是總價(jià)值為奇數(shù)直接不用考慮，而在DP的時(shí)候設(shè)置一個(gè)標(biāo)記來記錄是否已經(jīng)取得總價(jià)值一半，如果取得則可以返回。 做法2：這種方法的前提是POJ discuss里的一種做法，即給每個(gè)石頭的數(shù)量mod 8。證明是用抽屜原理證的，很復(fù)雜，我沒有看。但是這樣以來，數(shù)量 一下子大大減少，極大的提高了效率。 我說的做法2事實(shí)上是我的最初做法，即DFS，搜索，在搜索過程中注意剪枝，再加上數(shù)量取模的優(yōu)化，復(fù)雜度也不高。 Code for 1034(Dividing):
import java.util.Scanner;
import java.util.*;
import javax.swing.plaf.basic.BasicInternalFrameTitlePane.MaximizeAction;
public class Main {
public static int f[] = new int[20001*6]; // f[i]表示容量為 i 的背包最多能裝的物品的價(jià)值
public static int v[] = new int[7];
public static int num[] = new int[7];
public static int total,flag,key; //total為 6 種大理石的總價(jià)值 ，flag為標(biāo)記，一旦為1表示可以取得，可以返回了
public static void onezeropack(int cost,int weight) { // 01背包函數(shù)，注意循環(huán)是從total 到 cost，不要弄反
int i;
for(i = total;i >= cost; i--) {
f[i] = Math.max(f[i],f[i-cost]+weight);
if(f[i] == key) { // 如果可以取得總價(jià)值一半，flag=1，返回
flag = 1;
return ;
}
}
}
public static void finishpack(int cost,int weight) {
int i;
if(flag==1) return ;
for(i = cost;i <= total; i++) {
f[i] = Math.max(f[i], f[i-cost]+weight);
if(f[i] == key) {
flag = 1;
return ;
}
}
}
public static void multipack(int cost,int weight,int amount) {
if(cost*amount >= total) {
finishpack(cost, weight);
return ;
}
if(flag==1) return ;
int k = 1;
while(k < amount) { // 該過程即為將一件物品拆分為1，2，4...2^k 件物品進(jìn)行01背包過程
onezeropack(k*cost, k*weight);
amount -= k;
k *= 2;
}
onezeropack(cost*amount, weight*amount);
}
public static void main(String[] args){
Scanner in = new Scanner(System.in);
int i,j,cas = 1;
while(true) {
Arrays.fill(f,0);
total = 0; flag = 0;
for(i = 1;i <= 6; i++) {
num[i] = in.nextInt();
v[i] = i;
total += i*num[i];
}
if(num[1]==0&&num[2]==0&&num[3]==0&&num[4]==0&&num[5]==0&&num[6]==0)
break;
if(total%2==1) flag = 0;
else {
key = total/2;
for(i = 1;i <= 6; i++)
multipack(i, i, num[i]);
}
System.out.println("Collection #"+cas+":");
if(flag==0) System.out.println("Can't be divided.");
else System.out.println("Can be divided.");
System.out.println();
cas++;
}
}
}
TOJ 1670： 大意是一臺取款機(jī)有N中貨幣，每種貨幣面值為 V[i] ，數(shù)量為 num[i] , 給出一個(gè)價(jià)值，為在這個(gè)價(jià)值之內(nèi)(包括這個(gè)價(jià)值)最大能取得多大。 分析：典型的多重背包，給出的價(jià)值即為背包容量，每種貨幣為一種物品，價(jià)值為v[i] , 數(shù)量為num[i]，求能得到的最大價(jià)值。 注釋就不加了，參考上面的程序 Code for 1670(Cash Mechine):
#include <cstdio>
#include <cstring>
int f[100002],v[12],num[12],cost[12];
int total,n;
int max(int a,int b){ return a>b?a:b;}
void OneZeroPack(int cost,int value){
int i,j;
for(i = total;i >= cost; i--)
f[i] = max(f[i],f[i-cost]+value);
}
void completePack(int cost,int weight){
int i;
for(i = cost;i <= total; i++)
f[i] = max(f[i],f[i-cost]+weight);
}
void multiPack(int cost,int weight,int amount){
if(cost*amount >= total){
completePack(cost,weight);
return ;
}
int k = 1;
while(k < amount){
OneZeroPack(k*cost,k*weight);
amount -= k;
k*=2;
}
OneZeroPack(cost*amount,amount*weight);
}
int main(){
int i,j,k;
while(scanf("%d%d",&total,&n)!= EOF){
memset(f,0,sizeof(f));
for(i = 1;i <= n; i++){
scanf("%d%d",&num[i],&cost[i]);
v[i] = cost[i];
}
for(i = 1;i <= n; i++)
multiPack(cost[i],v[i],num[i]);
printf("%d\n",f[total]);
}
}
題目大意是N個(gè)人互相有債a[i](正的表示別人欠錢，否則表示自己欠別人錢,a[i]的和保證為0),但是這N個(gè)人只有朋友間才能互相算帳，現(xiàn)在給出N個(gè)人的債，并且給出M個(gè)關(guān)系，即誰和誰是朋友，最后問有沒有可能所有人都把帳算清。
Sample Input 1: Sample Input 2:
5 3 4 2
100 15
-75 20
-25 -10
-42 -15
42 0 2
0 1 1 3
1 2
3 4
Sample Output 1: Sample Output 2:
POSSIBLE IMPOSSILBE
思路1：
每輸入一個(gè)關(guān)系，合并，最后從1到N，對于每一個(gè)人，找出它們的祖先，將他們的債debt加到祖先的debt
上。通俗的講，就是每個(gè)集合的成員都將自己的debt加到祖先上，自己歸0，最后看祖先的值是否為0；
最后在從1到N掃一遍如果有debt不為0的，輸出“IMPOSSIBLE”，否則“POSSIBLE”；
缺點(diǎn)：復(fù)雜度高，查詢復(fù)雜度*N，最后勉強(qiáng)過了，時(shí)間0.63s
思路2：
路徑壓縮，每輸入一個(gè)關(guān)系，合并。最后從1到N，如果 i 的debt不為0，從 i 到 i 的祖先的路徑不斷壓縮直到
祖先，這樣雖然仍然是N次操作，但由于在壓縮過程中大部分成員debt歸0，故實(shí)際上進(jìn)行操作的次數(shù)遠(yuǎn)小于N.
最后時(shí)間為0.11,比起上一種方法有了很大提高
Code 1:
#include <cstdio>
#include <cstring>
struct Node{
int father,v,num;
}a[10002];
int find(int n){
int tep,m = n;
while(n != a[n].father)
n = a[n].father;
while(m != n){
tep = a[n].father;
a[n].father = n;
m = tep;
}
return n;
}
void Union(int root1,int root2){
int t1,t2;
t1 = find(root1),t2 = find(root2);
if(t1 == t2) return ;
else{
if(a[t1].v > a[t2].v){
a[t1].v += a[t2].v;
a[t2].father = t1;
}
else{
a[t2].v += a[t1].v;
a[t1].father = t2;
}
}
}
int main()
{
int n,m,i,j;
bool flag = false;
scanf("%d%d",&n,&m);
for(i = 0;i < n; ++i){
a[i].father = i,a[i].v = 0;
scanf("%d",&a[i].num);
}
while(m--){
scanf("%d%d",&i,&j);
Union(i,j);
}
for(i = 0;i < n; ++i){
int tep = find(i);
int tt = a[i].num;
a[i].num -= tt;
a[tep].num += tt;
}
for(i = 0;i < n; i++)
if(a[i].num != 0){
flag = true;
break;
}
if(flag) printf("IMPOSSIBLE\n");
else printf("POSSIBLE\n");
}
Code 2:
#include <cstdio>
#include <cstring>
struct Node{
int father,v,num;
}a[10002];
int find(int n){
int m = n,tep;
while(n != a[n].father)
n = a[n].father;
while(m != n){
tep = a[m].father;
int tt = a[m].num;
a[m].num -= tt;
a[tep].num += tt;
a[m].father = n;
m = tep;
}
return n;
}
void Union(int root1,int root2){
int t1,t2;
t1 = find(root1),t2 = find(root2);
if(t1 == t2) return ;
else{
if(a[t1].v > a[t2].v){
a[t1].v += a[t2].v;
a[t2].father = t1;
}
else{
a[t2].v += a[t1].v;
a[t1].father = t2;
}
}
}
int main()
{
int n,m,i,j;
bool flag = false;
scanf("%d%d",&n,&m);
for(i = 0;i < n; ++i){
a[i].father = i,a[i].v = 0;
scanf("%d",&a[i].num);
}
while(m--){
scanf("%d%d",&i,&j);
Union(i,j);
}
for(i = 0;i < n; ++i)
if(a[i].num != 0) find(i);
for(i = 0;i < n; i++)
if(a[i].num != 0){
flag = true;
break;
}
if(flag) printf("IMPOSSIBLE\n");
else printf("POSSIBLE\n");
}
這道題題意很難懂，大意是有N個(gè)公司，每個(gè)公司有一個(gè)center，最初每個(gè)公司的center都在自己公司，然后有M次操作，每次操作 A , B (A保證是一個(gè)集合的center，B不一定) 表示將A所在的集合并到B所在的集合，且B的center成為了A的center。每次操作后兩個(gè)公司的線的距離增加abs(A-B)%1000; Sample Input: (E P表示查詢P距離自己center的線的長度，I P Q 表示合并 P ,Q);
1
4
E 3
I 3 1
E 3
I 1 2
E 3
I 2 4
E 3
O
Sample Output:
0
2
3
5
Code:
#include <cstdio>
#include <iostream>
#define M 20010
using namespace std;
struct Node{
int father,num;
}a[M];
void initial(int n){
int i;
for(i = 1;i <= n; i++){
a[i].father = i;
a[i].num = 0;
}
}
int find(int n){
int tep,m = n;
if(n == a[n].father) return n;
find(a[n].father); //遞歸查找n的祖先
a[n].num += a[a[n].father].num; //n的直需要更新(加上n的父親的值)
a[n].father = a[a[n].father].father;
}
int main()
{
int T,n,i,j,k;
char order[3];
scanf("%d",&T);
while(T--){
scanf("%d",&n);
initial(n);
while(scanf("%s",order)){
if(order[0]== 'O') break;
if(order[0] == 'E'){
scanf("%d",&k);
find(k);
printf("%d\n",a[k].num);
}
else{
scanf("%d%d",&j,&k);
int dis = abs(j-k)%1000;
a[j].num = dis; //該值dis為j的值
a[j].father = k; //k成為了j的父親
}
}
}
}
題目給定一個(gè)進(jìn)制b，然后給兩個(gè)b進(jìn)制下的大數(shù) m 和 n ，要求求出m % n的結(jié)果，用b進(jìn)制表示。
最近在學(xué)JAVA，發(fā)現(xiàn)做起高精度簡直太爽了~ 這個(gè)題有JAVA簡直就是個(gè)水題，知道一些函數(shù)就好了。
BigInteger a = in.nextBigInteger(base); //將一個(gè)大數(shù)按照base進(jìn)制輸入
a.mod(b) ; //a%b,其中a和b都是大數(shù)且結(jié)果為10進(jìn)制，不管a和b是什么進(jìn)制
String str= a.toString(base); //將一個(gè)大數(shù)a轉(zhuǎn)換成b進(jìn)制的字符串
這個(gè)題就用到這些東西，代碼就不貼了。~~
很簡單的題，給定N個(gè)矩陣，然后給出一系列運(yùn)算式，用括號來限制運(yùn)算，最后求一共進(jìn)行了多少次乘法運(yùn)算。 R(m,s) 和Q(s,n)相乘，要進(jìn)行m*s*n次～ 處理運(yùn)算先后的時(shí)候，用棧實(shí)現(xiàn)，即后進(jìn)先出就可以了。 Sample Input:
9
A 50 10
B 10 20
C 20 5
D 30 35
E 35 15
F 15 5
G 5 10
H 10 20
I 20 25
A
B
C
(AA)
(AB)
(AC)
(A(BC))
((AB)C)
(((((DE)F)G)H)I)
(D(E(F(G(HI)))))
((D(EF))((GH)I))
Sample Outout:
0
0
0
error
10000
error
3500
15000
40500
47500
15125
Code:
#include <iostream>
#include <cstdio>
#include <string>
#include <map>
using namespace std;
struct Matrx{
char id;
int x,y;
}a[30];
Matrx stack[100];
int main()
{
int i,j,k,n,ans;
bool flag;
map<char,int>mark;
scanf("%d",&n);
for(i = 1;i <= n; i++){
cin >> a[i].id;
scanf("%d%d",&a[i].x,&a[i].y);
mark[a[i].id] = i;
}
string str;
while(cin>>str){
ans = 0; flag = true;
int len = str.length();
int head,tail;
head = tail = 0;
for(i = 0;i <len; i++){
if(str[i] == '(')
continue;
else if(str[i] == ')'){ //pop
if(head == 1)
head --;
else if(head > 1){
int tx = stack[head-2].x;
int ty = stack[head-1].y;
if(stack[head-2].y != stack[head-1].x) flag = false;
ans += stack[head-2].x*stack[head-2].y*stack[head-1].y;
head -= 2;
stack[head].x = tx;
stack[head++].y = ty;
}
}
else{ // push
stack[head++] = a[mark[str[i]]];
}
}
if(!flag) printf("error\n");
else printf("%d\n",ans);
}
}
給定從1 到 N的 N 個(gè)數(shù)，問有多少種不同方案劃分這些數(shù)。比如N = 3，則有5種方案：
{{1},{2},{3}}
{{1,2},{3}}
{{1,3},{2}}
{{2,3},{1}}
{{1,2,3}}
最后的結(jié)果只保留后四位，即mod10000；
上網(wǎng)查了下，集合的劃分的個(gè)數(shù)叫做bell數(shù)，bell數(shù)可以遞歸求解：
bell[0] = 1;
bell [n + 1] = sigma(C(n,k))*(bell[k]); (0<=k<=n)
然而這個(gè)題卻不可以這樣做，因?yàn)镹得范圍是2000，這樣做必定超時(shí)，于是想到了DP，如果用dp[i][j]表示i個(gè)數(shù)
劃分成j個(gè)集合，那么便有dp[i][j] = j * dp[i-1][j] + dp[i-1][j-1];( i > j )直觀理解就是，將i個(gè)數(shù)劃分成j個(gè)集合的個(gè)數(shù)，即為i-1個(gè)數(shù)劃分到j(luò)個(gè)集合的數(shù)，再將多的那個(gè)依次放到j(luò)個(gè)集合中，所以乘以j，或者是i-1個(gè)數(shù)放在j-1個(gè)集合中，第j個(gè)集合為空，則正好將多的這個(gè)數(shù)放到這個(gè)集合中，于是便有上邊的狀態(tài)轉(zhuǎn)移方程。
Code:
 #include <cstdio>
#include <iostream>
#include <cmath>
using namespace std;
int map[2002][2002];
  void DP() {
 memset(map,0,sizeof(map));
int i,j,k;
  for(i = 0;i <= 2000; i++){
map[i][i] = 1;
map[i][1] = 1;
 }
for(i = 0;i <= 2000 ;i++)
for(j = 0; j < i; j++)
map[i][j] = (j * map[i-1][j] + map[i-1][j-1])%10000;
 }
int main()
{
int i,j,k,n;
DP();
while(scanf("%d",&n),n){
int ans = 0;
for(i = 0;i <= n; i++)
ans = (ans + map[n][i])%10000;
string str = "0000";
str[3] = ans%10+'0'; ans/=10;
str[2] = ans%10+'0'; ans/=10;
str[1] = ans%10+'0'; ans/=10;
str[0] = ans%10+'0'; ans/=10;
cout<<str<<endl;
}
}
偏序集的兩個(gè)定理：
定理1) 令（X,≤）是一個(gè)有限偏序集，并令r是其最大鏈的大小。則X可以被劃分成r個(gè)但不能再少的反鏈。
其對偶定理稱為Dilworth定理：
定理2) 令（X,≤）是一個(gè)有限偏序集，并令m是反鏈的最大的大小。則X可以被劃分成m個(gè)但不能再少的鏈。
即：鏈的最少劃分?jǐn)?shù)=反鏈的最長長度
相關(guān)的題目有pku 1065，pku 3636，pku 1548
POJ 3636:
#include<iostream>
#include<algorithm>
#define M 20002
using namespace std;
struct Node{
int h,w;
}a[M];
int tail[M],n;
void LIS(int n){
int i,j,m,len,mid,low,high;
len=1;tail[1]=a[1].h;
for(i=2;i<=n;i++){
if(tail[len]<=a[i].h) {
len++;
tail[len]=a[i].h;
}
else{
low=1;high=len;
while(low<high){
mid=(low+high)/2;
if(a[i].h>=tail[mid]) low=mid+1;
else high=mid;
}
tail[low]=a[i].h;
}
}
printf("%d\n",len);
}
bool cmp(Node a,Node b){
if(a.w!=b.w)return a.w>b.w;
else return a.h<b.h;
}
int main()
{
int i,j,k,cas;
scanf("%d",&cas);
while(cas--){
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%d%d",&a[i].w,&a[i].h);
sort(a+1,a+1+n,cmp);
LIS(n);
}
//system("pause");
return 0;
}
POJ 1548:
#include<iostream>
#include<algorithm>
using namespace std;
int k,a[700],tail[800],b[860];
void LIS(){
int i,j,m,n,len,mid,left,right;
n=1;
for(i=k-1;i>=1;i--) b[n++]=a[i];
n--;
len=1;tail[1]=b[1];
for(i=2;i<=n;++i){
if(b[i]>tail[len]){
len++;
tail[len]=b[i];
}
else{
left=1;right=len;
while(left<right){ //二分查找插入的位置
mid=(left+right)/2;
if(tail[mid]<b[i]) left=mid+1;
else right=mid;
}
tail[left]=b[i]; //插入
}
}
printf("%d\n",len);
}
int main()
{
int i,j,m,n;
while(1){
k=1;
scanf("%d%d",&i,&j);
if(i==-1&&j==-1) break;
a[k++]=j;
while(scanf("%d%d",&i,&j)){
if(i==0&&j==0 ){
LIS();
break;
}
a[k++]=j;
}
}
}
|