国内精品久久久久久久久,亚洲精品蜜桃久久久久久,精品久久久久成人码免费动漫

此blog废掉啦~

M.J — Wed, 08 Dec 2010 14:59:00 GMT

误��?a style="COLOR: #800080" target=_blank>http://www.orzminjie.info/

M.J 2010-12-08 22:59 发表评论

M.J — Wed, 07 Jul 2010 17:14:00 GMT

              树的直径是指树的最长简单�\。求�? 两遍BFS :先�Q选一个�v点BFS扑ֈ�最长�\的终点，再从�l�点�q�行BFS�Q�则�W�二�ơBFS扑ֈ�的最长�\即�ؓ树的直径�Q?br>              原理: 设�v点�ؓu,�W�一�ơBFS扑ֈ�的终点v一定是树的直径的一个端�?br>              证明: 1) 如果u 是直径上的点�Q�则v昄��是直径的�l�点(因�ؓ如果v不是的话�Q�则必定存在另一个点w使得u到w的距��L��长，则于BFS扑ֈ�了v矛盾)
                      2) 如果u不是直径上的点，则u到v必然于树的直径相�?反证),那么交点到v 必然��是直径的后半段�?br>                       所以v一定是直径的一个端点，所以从v�q�行BFS得到的一定是直径长度

              相关题目有TOJ1056�Q�TOJ3517.

TOJ 1056(Labyrinth):
        大意是一个由‘#’�?.'构成的迷宫，'.'表示可行�Q?#8216;#’表示不可行，问可行的最长的路的长度是多��?br>

#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){                     //判断该点是否��界及是否可�?/span>
        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));         //初始所有点标记为false
        flag[start.x][start.y] = true;          //��L��标记为true
        queue<Node>f;
        while(!f.empty()) f.pop();                                                       //清空创徏的队�?/span>
        Node m,n,tep;
        int tx,ty,xx,yy;
        int i,j,k,num;
        f.push(start);
        while(!f.empty()){                                                                   //如果队列不�ؓ�I?/span>
                m = f.front();                       //取出队首元素
                tx = m.x; ty = m.y; num = m.num;
                if(num > maxt){                  //如果该元素的长度大于maxt�Q�更新maxt
                        maxt = num;
                        ans = m;
                }
                for(i = 0;i < 4; i++){               //以m��v点向4个方向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){                                            //如果有更大的则更�?/span>
                                        maxt = num + 1;
                                        ans = tep;
                                }
                        }
                }
                f.pop();                                   //弹出队首元素
        }
}
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]=='.'){ //任选一点BFS
                                        start.x = i;
                                        start.y = j;
                                        start.num = 0;
                                        bfs(start);
                                        mark = true;
                                        break;
                                }
                        }
                        if(mark) break;
                }
                maxt = -1;ans.num = 0;                   //此时ans一定是直径的端点，��它设�ؓ��L��
                bfs(ans);                                                                                    //�q�行�W�二�ơBFS
                printf("Maximum rope length is %d.\n",maxt);
        }
}

TOJ3517(The longest athletic track):
题目�l�出了一��는�成树�Q�问�q�棵生成树最长的路的长度是多��?br>

#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");
}

M.J 2010-07-08 01:14 发表评论

M.J — Wed, 07 Jul 2010 16:07:00 GMT

早就惛_��一下归�q�排序求逆序对，在这之前只会用树状数�l�来做，有时候还需要离散化�Q�而且效率�q�不如归�q�排序高�?br> 其实�q�是蛮简单的�Q�知道归�q�排序的原理��很�Ҏ��知道如何求逆序对了。设数组为A�Q�关键是在合�q�的时候，用数�l�L �?R 表示左右两个子数�l�，因�ؓ逆序对的个数f(A) = f(L) + f(R) + s(L,R);其中f(L) �?f(R) 分别表示L 内部和R内部的逆序对个敎ͼ�s(L.R)表示大数在L�Q�小数在R的逆序寏V��因为L和R是已�l�排好序的，故其实只需求s(L,R).�q�个可以在合�q�L和R依次�q�行比较的时候算出�?br>

for(k = p;k <= r;k ++){
          if(L[i]<=R[j])
                  a[k] = L[i++];
          else{                                                //如果L最上面的数大于R的，那么L[i]及后面的数可以和R[j]构成n1-i+1个逆序�?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);
          }
}

M.J 2010-07-08 00:07 发表评论

多重背包问题

M.J — Wed, 07 Jul 2010 12:18:00 GMT

今天看了下多重背包，理解的还不够深入�Q�不�q�因为是01背包�q�来的，所以接受�v来很�Ҏ��?br>主要是运用了二进制的思想��一个数量�ؓN很大的物品分��Z��logN个数量小的物品，而这logN个物品可以组成数量�ؓ0到N��L��数量�Q�所以这�U�策略是
成立的�?br>多重背包问题有TOJ1034�Q�TOJ1670.

TOJ1034 :
大意是有6�U�规格的矛_��Q�编号从1�?�Q�编号�ؓ i 的石头的价��gؓ i .现在�l�出各种矛_��的数量，问有没有可能得到��M�h值的一半�?br>做法: DP, 每种矛_��价��gؓv[i],价��gؓ i �Q�数量�ؓ num[i] ,通过多重背包看能不能恰好取得��M�h值的一半�?br> 一个优化是��M�h��gؓ奇数直接不用考虑�Q�而在DP的时候设�|�一个标记来记录是否已经取得��M�h��g��半，如果取得则可以返回�?br>做法2�Q�这�U�方法的前提是POJ discuss里的一�U�做法，即给每个矛_��的数量mod 8。证明是用抽屉原理证的，很复杂，我没有看。但是这样以来，数量
一下子大大减少�Q�极大的提高了效率�?br> 我说的做�?事实上是我的最初做法，即DFS�Q�搜索，在搜索过�E�中注意剪枝�Q�再加上数量取模的优化，复杂度也不高�?nbsp;

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]表示定w��?i 的背包最多能装的物品的�h�?br>    public static int v[] = new int[7];
    public static int num[] = new int[7];
    public static int total,flag,key;                                                             //total�?6 �U�大理石的��M�h�?�Q�flag为标讎ͼ�一旦�ؓ1表示可以取得�Q�可以返回了
    public static void onezeropack(int cost,int weight) {             // 01背包函数�Q�注意��@环是从total �?cost�Q�不要弄�?br>            int i;
      for(i = total;i >= cost; i--) {
              f[i] = Math.max(f[i],f[i-cost]+weight);
              if(f[i] == key) {                                                                 // 如果可以取得��M�h��g��半，flag=1�Q�返�?br>                  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) {                                                                                        // 该过�E�即为将一件物品拆分�ؓ1�Q?�Q?...2^k 件物品进�?1背包�q�程
                            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�Q?br> 大意是一台取�ƾ机有N中货币，每种货币面��gؓ V[i] �Q�数量�ؓ num[i] , �l�出一个�h��|��为在�q�个价��g��?包括�q�个价�?最大能取得多大�?br>分析�Q�典型的多重背包�Q�给出的价值即��包容量，每种货币��Z��U�物品，价��gؓv[i] , 数量为num[i]�Q�求能得到的最大�h倹{�?br> 注释��׃��加了�Q�参考上面的�E�序

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]);
           }
}

M.J 2010-07-07 20:18 发表评论

TOJ 3446.Money Matters �q�查集，路径压羃

M.J — Mon, 05 Jul 2010 13:08:00 GMT

        题目大意是N个�h互相有债a[i](正的表示别�h�Ơ钱�Q�否则表�C��己欠别�h�?a[i]的和保证�?),但是�q�N个�h只有朋友间才能互相算帐，现在�l�出N个�h的债，�q�且�l�出M个关�p�，卌��和谁是朋友，最后问有没有可能所有�h都把帐算清�?br>

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�Q?/font> 每输入一个关�p�，合�ƈ�Q�最后从1到N�Q�对于每一个�h�Q�找出它们的��先�Q�将他们的债debt加到��先的debt 上。通俗的讲�Q�就是每个集合的成员都将自己的debt加到��先上，自己�?�Q�最后看��先的值是否�ؓ0�Q?/font> 最后在�?到N扫一遍如果有debt不�ؓ0的，输出“IMPOSSIBLE”�Q�否�?#8220;POSSIBLE”�Q?/font> �~�点�Q�复杂度高，查询复杂�?N�Q�最后勉��了，旉��0.63s 思�\2�Q?/font> 路径压羃�Q�每输入一个关�p�，合�ƈ。最后从1到N�Q�如�?i 的debt不�ؓ0�Q�从 i �?i 的祖先的路径不断压羃直到 ��先�Q�这栯��然仍然是N�ơ操作，但由于在压羃�q�程中大部分成员debt�?�Q�故实际上进行操作的�ơ数�q�小于N. 最后时间�ؓ0.11,比�v上一�U�方法有了很大提�?/font> 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"); }

M.J 2010-07-05 21:08 发表评论

M.J — Mon, 05 Jul 2010 12:48:00 GMT

       �q�道题题意很难懂�Q�大意是有N个公司，每个公司有一个center�Q�最初每个公司的center都在自己公司�Q�然后有M�ơ操作，每次操作 A , B (A保证是一个集合的center�Q�B不一�? 表示��A所在的集合�q�到B所在的集合�Q�且B的center成�ؓ了A的center。每�ơ操作后两个公司的线的距��d��加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 OSample 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的祖�?/tt>         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的�?/tt>                                 a[j].father = k;         //k成�ؓ了j的父�?/tt>                         }                 }         } }M.J 2010-07-05 20:48 发表评论

M.J — Wed, 23 Jun 2010 08:05:00 GMT 题目�l�定一个进制b�Q�然后给两个b�q�制下的大数 m �?n �Q�要求求出m % n的结果，用b�q�制表示�?br>最�q�在学JAVA�Q�发现做起高�_�ֺ��直太爽了~ �q�个题有JAVA��直就是个水题�Q�知道一些函数就好了�?br>BigInteger a = in.nextBigInteger(base); //��一个大数按照base�q�制输入 a.mod(b) ; //a%b,其中a和b都是大数且结果�ؓ10�q�制�Q�不��a和b是什么进�?br>String str= a.toString(base); //��一个大数a转换成b�q�制的字�W�串 �q�个题就用到�q�些东西�Q�代码就不脓了。~~ M.J 2010-06-23 16:05 发表评论 TOJ 1135 Matrix Chain Multiplication M.J — Sat, 12 Jun 2010 14:10:00 GMT 很简单的题，�l�定N个矩阵，然后�l�出一�p�d��q�算式，用括��h��限制�q�算�Q�最后求一��p��行了多少�ơ乘法运��?br>R(m,s) 和Q(s,n)�怹��Q�要�q�行m*s*n�ơ～处理�q�算先后的时候，用栈实现�Q�即后进先出��可以了�?br>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); } } M.J 2010-06-12 22:10 发表评论【DP】TOJ 2820 How many different ways M.J — Sat, 12 Jun 2010 07:05:00 GMT �l�定�? �?N�?N 个数�Q�问有多��种不同�Ҏ��划分�q�些数。比如N = 3�Q�则�?�U�方案： {{1},{2},{3}} {{1,2},{3}} {{1,3},{2}} {{2,3},{1}} {{1,2,3}} 最后的�l�果只保留后四位�Q�即mod10000�Q?br>上网查了下，集合的划分的个数叫做bell敎ͼ�bell数可以递归求解�Q?br>bell[0] = 1; bell [n + 1] = sigma(C(n,k))*(bell[k]); (0<=k<=n) 然而这个题却不可以�q�样做，因�ؓN得范围是2000�Q�这样做必定��时�Q�于是想��C��DP�Q�如果用dp[i][j]表示i个数划分成j个集合，那么便有dp[i][j] = j * dp[i-1][j] + dp[i-1][j-1];( i > j )直观理解��是�Q�将i个数划分成j个集合的个数�Q�即为i-1个数划分到j个集合的敎ͼ�再将多的那个依次攑ֈ�j个集合中�Q�所以乘以j�Q�或者是i-1个数攑֜�j-1个集合中�Q�第j个集合�ؓ�I�，则正好将多的�q�个数放到这个集合中�Q�于是便有上边的状态�{�U�L��E��?br>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; } } M.J 2010-06-12 15:05 发表评论 M.J — Fri, 28 May 2010 10:35:00 GMT 偏序集的两个定理�Q?br>定理1) 令（X,≤�Q�是一个有限偏序集�Q��ƈ令r是其最大链的大��。则X可以被划分成r个但不能再少的反链�?br>其对偶定理称为Dilworth定理�Q?br>定理2) 令（X,≤�Q�是一个有限偏序集�Q��ƈ令m是反铄��最大的大小。则X可以被划分成m个但不能再少的链�?br> 卻I��铄��最��划分数=反链的最镉K��?br>相关的题目有pku 1065�Q�pku 3636�Q�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){ //二分查找插入的位�|?nbsp; 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; } } } M.J 2010-05-28 18:35 发表评论