Bài toán nối điểm
#1
Đã gửi 29-03-2016 - 12:52
- PUA yêu thích
Master Kaiser
Liên hệ facebook : https://www.facebook...uyenhoanganh238
#2
Đã gửi 17-04-2016 - 10:08
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
#3
Đã gửi 17-04-2016 - 10:10
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;
}
#4
Đã gửi 17-04-2016 - 14:28
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 ?
>>> Nếu bạn luôn buồn phiền hãy dùng hy vọng để chữa trị <<<
Và ...
>>> Không bao giờ nói bạn đã thất bại
Cho đến khi đó là nỗi lực cuối cùng của bạn
Và không bao giờ nói rằng:
Đó là nỗi lực cuối cùng của bạn
Cho tới khi bạn đã thành công >>>
~ Mystic Lâm
#5
Đã gửi 17-04-2016 - 20:43
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
- PUA yêu thích
Master Kaiser
Liên hệ facebook : https://www.facebook...uyenhoanganh238
#6
Đã gửi 17-04-2016 - 20:48
Bài viết đã được chỉnh sửa nội dung bởi Master Kaiser: 17-04-2016 - 21:01
- PUA yêu thích
Master Kaiser
Liên hệ facebook : https://www.facebook...uyenhoanganh238
0 người đang xem chủ đề
0 thành viên, 0 khách, 0 thành viên ẩn danh