2013-07-07 22:21:39Morris
[UVA][dp][BIT] 11240 - Antimonotonicity
Problem B: Antimonotonicity
I have a sequence Fred of length n comprised of integers between 1 and n inclusive. The elements of Fred are pairwise distinct. I want to find a subsequence Mary of Fred that is as long as possible and has the property that:Mary[0] > Mary[1] < Mary[2] > Mary[3] < ...
Input
The first line of input will contain a single integer T expressed in decimal with no leading zeroes. T will be at most 50. T test cases will follow.Each test case is contained on a single line. A line describing a test case is formatted as follows:
n Fred[0] Fred[1] Fred[2] ... Fred[n-1].where n and each element of Fred is an integer expressed in decimal with no leading zeroes. No line will have leading or trailing whitespace, and two adjacent integers on the same line will be separated by a single space. n will be at most 30000.
Output
For each test case, output a single integer followed by a newline --- the length of the longest subsequence Mary of Fred with the desired properties.Sample Input
4 5 1 2 3 4 5 5 5 4 3 2 1 5 5 1 4 2 3 5 2 4 1 3 5
Sample Output
1 2 5 3
Tor Myklebust
題目是要找一個高低高低 ... 的子序列，但是一開始一定要是高的。
跟 LIS 的做法差不多，但需要維護上一次是接 > 還是 <。
因此這裡使用 binary indexed tree 進行維護。
當接下來要將這個數字前面擺放 >，那麼要在前一次接 < 調查比它大的數字。
當接下來要將這個數字前面擺放 <，那麼要在前一次接 > 調查比它小的數字。
由於 binary indexed tree 操作只能查 1 ... index 的總合或者最大值。
因此，將調查比它大的數字的數據上做一個映射處理，讓它變得可以查比它大的數字。
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
int BIT[2][32767];//[0] prev <, [1] prev >
int A[32767];
void modify(int row, int idx, int val, int L) {
while(idx <= L) {
BIT[row][idx] = max(BIT[row][idx], val);
idx += idx&(-idx);
}
}
int query(int row, int idx) {
int ret = 0;
while(idx) {
ret = max(ret, BIT[row][idx]);
idx -= idx&(-idx);
}
return ret;
}
int main() {
/*freopen("in.txt", "r+t", stdin);
freopen("out.txt", "w+t", stdout);*/
int testcase, n;
int i, j;
scanf("%d", &testcase);
while(testcase--) {
scanf("%d", &n);
for(i = 0; i < n; i++)
scanf("%d", &A[i]);
memset(BIT, 0, sizeof(BIT));
int ret = 0;
for(i = 0; i < n; i++) {
int dp1 = 0, dp2 = 0;//< A[i], > A[i]
dp1 = query(1, A[i]-1)+1;
dp2 = query(0, n-A[i])+1;
if(dp1 == 2) dp1 = 1;
ret = max(ret, dp1);
ret = max(ret, dp2);
modify(0, n-A[i]+1, dp1, n);
modify(1, A[i], dp2, n);
}
printf("%d\n", ret);
}
return 0;
}/*
20
10 3 9 6 9 2 2 8 3 6 7
*/