Chủ đề này có 5 trả lời

[Master Kaiser]

" Trên hai đuờng thẳng song song L1 và L2, Người ta đánh dấu trên mỗi đường N 

Điểm, Các điểm  trên đường  thẳng L1 Được đánh số từ 1 đến N, từ  trái qua phải,  

còn các điểm  trên đường  thẳng L2 được đánh số bởi P[1],P[2],...P[N] cũng từ  trái 

qua phải, trong đó P[1],P[2],..P[N] là một hoán vị của các số 1,2,...N  

Ta gọi các số gán cho các điểm là số hiệu của chúng. Cho phép nối hai điểm trên 2 

đường thẳng có cùng số hiệu. 

Yêu Cầu  : Tìm cách nối được nhiều cặp điểm nhất với điều kiện các đoạn nối không 

được cắt nhau.  

Dữ Liệu : Vào từ File BaiToan2.Inp: 

•  Dòng đầu tiên chứa số nguyên dương N(N<=1000) 

•  Dòng thứ hai chứa các số P[1],P[2],....P[N] 

Kết Quả Ghi Ra File : BaiToan2.Out  

•  Dòng Đầu tiên chứa K là số lượng đoạn nối tìm được 

•  Dòng tiếp theo chứa K số hiệu của các đầu mút của các đoạn nối được ghi theo thứ 

tự tăng dần.  

Ví Dụ : 

      WIRES.INP          WIRES.OUT 

9   5 

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

--------------------------------------------

Cho mình xin code nha

[hoicmvsao]

Bài này giải giống bài LIS là được. Tìm dãy con tăng dìa nhất của P[i] rồi xuất ra độ dài là được

[hoicmvsao]

Mình chỉ có code bằng C++ thôi.

#include <bits/stdc++.h>
#define F(i,a,b)    for (int i=a;i<=b;i++)
#define D(i,a,b)    for (int i=a;i>=b;i--)
using namespace std;
int n,p[1001],kq[1001]={0},trace[1001]={0};
void open()
{
    freopen("Wires.inp","r",stdin);
    freopen("Wires.out","w",stdout);
}
void read()
{
    cin>>n;
    F(i,1,n) cin>>p[i];
    p[0]=0;
    p[n+1]=n+1;
}
void qhd()
{       int c[1001];
        F(i,1,n+1)
            F(j,0,i-1) if (p[j]<p[i]) if (kq[i]<kq[j]+1){kq[i]=kq[j]+1; trace[i]=j;};

        int j=trace[n+1];
        int k=kq[n+1]-1;
        cout<<k<<endl;
        int l=k;
        while(j>0)
        {
            c[k]=p[j];
            j=trace[j];
            k--;
        }
        F(i,1,l) cout<<c[i]<<" ";
}
int main()
{   open();
    read();
    qhd();
    return 0;
}
 

[Mystic]

Mình chỉ có code bằng C++ thôi.

#include <bits/stdc++.h>
#define F(i,a,b)    for (int i=a;i<=b;i++)
#define D(i,a,b)    for (int i=a;i>=b;i--)
using namespace std;
int n,p[1001],kq[1001]={0},trace[1001]={0};
void open()
{
    freopen("Wires.inp","r",stdin);
    freopen("Wires.out","w",stdout);
}
void read()
{
    cin>>n;
    F(i,1,n) cin>>p[i];
    p[0]=0;
    p[n+1]=n+1;
}
void qhd()
{       int c[1001];
        F(i,1,n+1)
            F(j,0,i-1) if (p[j]<p[i]) if (kq[i]<kq[j]+1){kq[i]=kq[j]+1; trace[i]=j;};

        int j=trace[n+1];
        int k=kq[n+1]-1;
        cout<<k<<endl;
        int l=k;
        while(j>0)
        {
            c[k]=p[j];
            j=trace[j];
            k--;
        }
        F(i,1,l) cout<<c[i]<<" ";
}
int main()
{   open();
    read();
    qhd();
    return 0;
}
 

Bạn làm ra pascal cho mình xem đc ko ?

[Master Kaiser]

 

Bạn làm ra pascal cho mình xem đc ko ?

mình làm đc pascal ruj

Cái pic này từ lâu rồi :3

Bài viết đã được chỉnh sửa nội dung bởi Master Kaiser: 17-04-2016 - 20:59

[Master Kaiser]

PROGRAM Bai_toan_noi_diem;

uses crt;

var f:text;

    N,slx:integer;

    a,sl,tr,x:array[1..1000] of integer;

procedure Docdl;

          var i,u:integer;

          begin

               assign(f,'WIRES.INP');reset(f);readln(f,N);

               for i:=1 to N do

                   begin

                        read(f,u);a[u]:=i;

                   end;

               close(f);

          end;

procedure XDB;

          var i,j:integer;

          begin

               sl[1]:=1;tr[1]:=-1;

               for i:=2 to N do

                   begin

                        sl[i]:=1;tr[i]:=-1;

                        for j:=i-1 downto 1 do

                            if (a[j]<a[i]) and (sl[i]<sl[j]+1) then

                               begin

                                    sl[i]:=sl[j]+1;Tr[i]:=j;

                               end;

                   end;

          end;

procedure XLB;

          var u,i:integer;

          begin

               u:=1;

               for i:=2 to N do

                   if sl[i]>sl[u] then u:=i;

               slx:=0;

               repeat

                     inc(slx);x[slx]:=u;u:=tr[u];

               until u=-1;

          end;

procedure Inkq;

          var i:integer;

          begin

               assign(f,'WIRES.OUT'); rewrite(f);writeln(f,slx);

               for i:=slx downto 1 do write(f,x[i],' ');

               close(f);

          end;

BEGIN

   Docdl;XDB;XLB;Inkq;

END.

Bài viết đã được chỉnh sửa nội dung bởi Master Kaiser: 17-04-2016 - 21:01