题是水题,学习一下用树状数组求LIS。
先离散化一下,注意去重;然后就把a[i]作为下标,dp[i]作为值,max作为维护的运算插进树状数组即可。
如果是上升子序列,询问(a[i] - 1);如果是不下降子序列,询问(a[i])。
1 const int maxn = 1e3 + 5; 2 int n, m, a[maxn], b[maxn], dp[maxn], f[maxn]; 3 4 void Modify(int x, int val) { 5 for (; x <= m; x += x&-x) 6 f[x] = max(f[x], val); 7 } 8 9 int Query(int x) { 10 int ret = 0; 11 for (; x; x -= x&-x) 12 ret = max(f[x], ret); 13 return ret; 14 } 15 16 int main() { 17 while (~scanf("%d", &n) && n) { 18 init(f, 0); 19 rep(i, 1, n) read(a[i]), b[i] = a[i]; 20 //离散化 21 sort(b + 1, b + 1 + n); 22 m = unique(b + 1, b + 1 + n) - b - 1; 23 rep(i, 1, n) a[i] = lower_bound(b + 1, b + 1 + m, a[i]) - b; 24 25 int ans = 0; 26 rep(i, 1, n) { 27 dp[i] = Query(a[i] - 1) + b[a[i]]; 28 ans = max(ans, dp[i]); 29 Modify(a[i], dp[i]); 30 } 31 32 writeln(ans); 33 } 34 return 0; 35 }