hdu1025 最大遞增子序列
把題意轉換一下就是最大遞增子序列問題 不過就是數的排列不是按輸入順序
500000果斷用n*logN的時間復雜度
這個算法是把每個數一個個往裡面插入 然後一步步更新len（當前最大子序列） 最後得出全局的最大子序列
num【i】表示數i出現的位置 dis【k】表示子序列長度為k的出現的最小的位置（比如x=dis【k】表示最先出現子序列為k的位置為x）
注意for循環跑到i表示以num【i】結尾的最大子序列
現在就出現兩種情況
1》dis【len】
2》dis【len】》num【i】 然後用二分查找到最小的j是dis【j】>num【i】；令dis【j】=num【i】 注意討論沒有的情況
下面是詳細代碼
#include
#include
#include
using namespace std;
int dis[500010],num[500010];
int main()
{
int n,i,j,a,b,d=1;
while(~scanf("%d",&n))
{
for(i=1;i<=n;i++)
{
scanf("%d%d",&a,&b);
num[a]=b;
}
int len=1;
int L,R;
dis[1]=num[1];
for(i=2;i<=n;i++)
{
if(dis[len]<num[i])
{
len++;
dis[len]=num[i];
}
else if(dis[len]>num[i])
{
L=1;
R=len;
int flash=0;
while(L<=R)
{
int mid=(L+R)/2;
if(dis[mid]<num[i]) L=mid+1;
else if(dis[mid]>num[i])R=mid-1;
else {flash==1;break;}
}
if(!flash)dis[L]=num[i];
}
}
printf("Case %d:\n",d++);
if(len==1) printf("My king, at most 1 road can be built.");
else printf("My king, at most %d roads can be built.",len);
printf("\n");
printf("\n");
}
return 0;
}
