2012-11-10 10:46:54Morris
[ZJ][BIT] a572. IS&MS
內容 ：
| IS&MS |
Background
在寫 a569: 2-絕對遞增的質數子數列 的時候，小光一眼就看錯題目了，結果錯得亂七八糟，可見小光的語文能力多差勁！
The Problem
求一個最大總合的嚴格遞增子序列。[14 14 9 11 1 19] =>[9 11 19] 總和為 39。
輸入說明
：
多組測資，每組兩行，
每組一行有一個數字 N，代表接下來有 N 個數字。
每組第二行，有 N 個正數字 Ai。
1 ≦ N ≦ 10000，1 ≦ Ai ≦ 1,000,000
輸出說明
：
每組一行，輸出最大總合。
範例輸入
：
6
14 14 9 11 1 19
5
16 9 10 13 17
範例輸出 ：
39 49
提示
：
※ 題目重覆請通知我。
※ 沒有要求質數，很明顯的 9 不是質數。
出處
：
(管理：morris1028)
用的 binary indexed tree 去完成查詢。
先將測資離散化，之後調查 max(BIT[k]) 0<k<v[j] 代表能接的最大值。
原本 O(n*n) 是這麼寫的 dp[i] = max(dp[j])+A[i] (j < i && A[i] > A[j])
使用 BIT 降至 O(nlogn)。
有其他作法歡迎提出來，這方法可能不夠好。
/**********************************************************************************/用的 binary indexed tree 去完成查詢。
先將測資離散化，之後調查 max(BIT[k]) 0<k<v[j] 代表能接的最大值。
原本 O(n*n) 是這麼寫的 dp[i] = max(dp[j])+A[i] (j < i && A[i] > A[j])
使用 BIT 降至 O(nlogn)。
有其他作法歡迎提出來，這方法可能不夠好。
/* Problem: a572 "IS&MS" from */
/* Language: CPP (1215 Bytes) */
/* Result: AC(104ms, 780KB) judge by this@ZeroJudge */
/* Author: morris1028 at 2012-11-08 18:34:16 */
/**********************************************************************************/
#include <stdio.h>
#include <algorithm>
#include <map>
using namespace std;
int lowbit[10005];
long long C[10005];
void modify(int idx, int L, long long v) {
while(idx <= L) {
C[idx] = max(C[idx], v);
idx += lowbit[idx];
}
}
long long query(int idx) {
static long long ans;
ans = 0;
while(idx) {
ans = max(ans, C[idx]);
idx -= lowbit[idx];
}
return ans;
}
int main() {
int n, i, A[10005];
for(i = 0; i < 10005; i++)
lowbit[i] = i&(-i);
while(scanf("%d", &n) == 1) {
map<int, int> r;
for(i = 0; i < n; i++) {
scanf("%d", &A[i]);
r[A[i]] = 1;
}
int idx = 1, tn, tag;
for(map<int, int>::iterator it = r.begin();
it != r.end(); it++) {
C[idx] = 0;
it->second = idx++;
}
tn = idx;
long long pred, ans = 0;
for(i = 0; i < n; i++) {
tag = r[A[i]];
pred = query(tag-1);
modify(tag, tn, pred+A[i]);
if(pred+A[i] > ans)
ans = pred+A[i];
}
printf("%lld\n", ans);
}
return 0;
}