HDU 2227 Find the nondecreasing subsequences(세그먼트 트리 최적화 DP)
제목: n개 수를 주고 비체감 서열의 개수를 구하세요.
사고방식: d[i]로 표시하고 a[i]를 마지막 원소의 비감자 서열 개수로 한다.그러면 매번 이동할 때마다sum(d[j])(그중 j그러면 최종 답은 모든 d[i](1<=i<=n)의 합이다.
자세한 참고 코드:
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<bitset>
#include<cstdlib>
#include<cmath>
#include<set>
#include<list>
#include<deque>
#include<map>
#include<queue>
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
using namespace std;
typedef long long ll;
typedef long double ld;
const ld eps = 1e-9, PI = 3.1415926535897932384626433832795;
const int mod = 1000000000 + 7;
const int INF = 0x3f3f3f3f;
// & 0x7FFFFFFF
const int seed = 131;
const ll INF64 = ll(1e18);
const int maxn = 100000 + 10;
int T,n,m;
ll sum[maxn<<2], d[maxn],a[maxn],b[maxn];
inline void add(ll& a, ll b) {
a += b;
if(a >= mod) a %= mod;
}
void pushup(int o) {
sum[o] = sum[o<<1] + sum[o<<1|1];
if(sum[o] >= mod) sum[o] %= mod;
}
void build(int l, int r, int o) {
int m = (l + r) >> 1;
sum[o] = 0;
if(l == r) return ;
build(l, m, o<<1);
build(m+1, r, o<<1|1);
pushup(o);
}
void update(int L, int R, ll v, int l, int r, int o) {
int m = (l + r) >> 1;
if(L <= l && r <= R) {
add(sum[o], v); return ;
}
if(L <= m) update(L, R, v, l, m, o<<1);
if(m < R) update(L, R, v, m+1, r, o<<1|1);
pushup(o);
}
ll query(int L, int R, int l, int r, int o) {
int m = (l + r) >> 1;
if(L <= l && r <= R) return sum[o];
ll ans = 0;
if(L <= m) add(ans, query(L, R, l, m, o<<1));
if(m < R) add(ans, query(L, R, m+1, r, o<<1|1));
return ans;
}
int main() {
while(~scanf("%d",&n)) {
for(int i=1;i<=n;i++) {
scanf("%I64d",&a[i]);
b[i-1] = a[i];
}
sort(b, b+n);
int len = unique(b, b+n) - b;
build(1, len, 1);
for(int i=1;i<=n;i++) {
int r = lower_bound(b, b+len, a[i]) - b + 1;
ll cur = query(1, r, 1, len, 1);
d[i] = 1;
add(d[i], cur);
update(r, r, d[i], 1, len, 1);
}
printf("%I64d
",query(1, len, 1, len, 1));
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
백준 알고리즘 14427번 : 수열과 쿼리 15길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i v : Ai를 v로 바꾼다. (1 ≤ i ≤ N, 1 ≤ v ≤ 109) 2 : 수열에서 크기가 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.