POJ2533
POJ2533
package Week3;
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
//最长递增子序列，DP+二分查找
//7
//1 7 3 5 9 4 8
//输出文件必须包含单个整数 - 给定序列中最长的有序子序列的长度。
//思路：开一个跟原数组大小一样大的数组
//第一个值直接放进去，count=1
//从第二个开始跟数组中的值比较如果大于数组中arr[count-1]直接补到数组最后边，然后count++
//从第二个开始跟数组中的值比较如果小于数组中arr[count-1]找第一个不小于它的数（binarySearch如果idx负值则取绝对值然后减一就是你要替换的位置）替换
public class POJ2533_DP {
static int N;
static int arr[];
static int count;
public static void main(String[] args) throws Exception{
System.setIn(new FileInputStream("Solution.txt"));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = null;
while(br.ready()) {
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
arr = new int[N+1];
count = 0;//目前为止最长递增子序列的个数
st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
if(i==0) {
arr[0]=Integer.parseInt(st.nextToken());
count=count+1;
}else {
int x = Integer.parseInt(st.nextToken());
if(x>arr[count-1]) {//新读进来的值跟arr里最后一个值比较如果大于arr最大值，直接补在最后边且count++
arr[count]=x;
count=count+1;
}else {//新读进来的值，小于arr里最后一个值，那就二分查找，找第一个不小于它的数，替换掉
//找出来不小于它的数找到了，直接替换，没找到就取绝对值减一位置替换
int idx = Arrays.binarySearch(arr, 0, count, x);
if(idx>=0) {
arr[idx]=x;
} else {
arr[Math.abs(idx)-1]=x;
}
}
}
}
System.out.println(count);
}
}
}
package Week3;
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
//7
//1 7 3 5 9 4 8
//求最长递增子序列的长度用indextree求解
public class POJ2533_Index {
static int N;
static int arr[];
static int tree[];
static int ans;
static PriorityQueue<NodeW> pq = new PriorityQueue<NodeW>(11,new Comparator<NodeW>() {
@Override
public int compare(NodeW o1, NodeW o2) {
return o1.val == o2.val?o2.idx-o1.idx:o1.val-o2.val; //值升序排序，值相等时，索引降序
}
});
public static void main(String[] args) throws Exception{
System.setIn(new FileInputStream("Solution.txt"));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = null;
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
arr = new int[N+1];
int L =1;
while(L<N) {
L = L+L;
}
tree = new int[2*L];
st = new StringTokenizer(br.readLine());
for (int i = 1; i <= N; i++) {
int val = Integer.parseInt(st.nextToken());
pq.add(new NodeW(i,val));
}
while(!pq.isEmpty()) {
NodeW node = pq.poll();
int idx = node.idx;
// int val = node.val;
int res = query(L,idx+L-1-1);//查叶节点第一个到该数位置前一个节点为止最长递增子序列的长度然后update更新加1
update(idx+L-1,res+1);
}
System.out.println(tree[1]);
}
private static void update(int idx, int val) {
tree[idx]=val;
idx = idx/2;
while(idx>0) {
tree[idx]=Math.max(tree[idx*2], tree[idx*2+1]);
idx = idx/2;
}
}
private static int query(int s, int e) {
int result = 0;
while(s<=e) {
if(s%2==1) {
result=result<tree[s]?tree[s]:result;
}
if(e%2==0) {
result= result<tree[e]?tree[e]:result;
}
s = (s+1)/2;
e = (e-1)/2;
}
return result;
}
}
class NodeW {
int idx;
int val;
public NodeW(int idx,int val) {
this.idx = idx;
this.val = val;
}
}
package Week3;
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.StringTokenizer;
import java.util.TreeSet;
//7
//1 7 3 5 9 4 8
//求最长递增子序列的长度用indextree加散列话求解
public class POJ2533_SanLieHua {
static int N;
static int arr[][];
static int tree[];
static int ans;
static TreeSet<Integer> set = new TreeSet<Integer>();
static HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
public static void main(String[] args) throws Exception{
System.setIn(new FileInputStream("Solution.txt"));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = null;
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
arr = new int[N+1][2];
int L =1;
while(L<N) {
L = L+L;
}
tree = new int[2*L];
st = new StringTokenizer(br.readLine());
set.clear();
for (int i = 1; i <= N; i++) {
int val = Integer.parseInt(st.nextToken());
arr[i][0]=i;
arr[i][1]=val;
set.add(val);//1 7 3 5 9 4 8
}
map.clear();
int k = 1;
while (!set.isEmpty()) {
map.put(set.pollFirst(), k++);//1=1 3=2 4=3 5=4 7=5 8=6 9=10
}
for (int i = 1; i <= N; i++) {
int idx = map.get(arr[i][1]);
int q = query(L,L+idx-1-1);
update(L+idx-1,q+1);
}
System.out.println(tree[1]);
}
private static void update(int idx, int val) {
tree[idx]=val;
idx = idx/2;
while(idx>0) {
tree[idx]=Math.max(tree[idx*2], tree[idx*2+1]);
idx = idx/2;
}
}
private static int query(int s, int e) {
int result = 0;
while(s<=e) {
if(s%2==1) {
result=result<tree[s]?tree[s]:result;
}
if(e%2==0) {
result= result<tree[e]?tree[e]:result;
}
s = (s+1)/2;
e = (e-1)/2;
}
return result;
}
}