편차 관계와 dp BZOJ3594(2D 트리 배열)
편차 관계
2D 트리 배열
이 문제는 dp[i][j]로 앞의 i 개수를 표시하고 h[i]로 끝내며 j회 수정, 가장 긴 비체감 서열을 사용했다.
그런데 이렇게 직접 dp로 하면 다음과 같습니다.
for(int i=1; i<=n; i++){
for(int j=0; j<=K; j++){
for(int a=0; a=h[a])
dp[i][j]=max(dp[i][j], dp[a][b]+1);
}
}
}
}시간 초과입니다.이 문제는 교묘하게 편차 관계를 이용하여 2차원 트리 모양의 수조로 시간을 n*k*logn*logk로 최적화시킨다.
옮길 수 있다면 h[i]+j-b>=h[a]의 조건을 충족시켜야 한다. 즉, h[i]+j>=h[a]+b, 전제는 i>a, j>=b이다. 그러면 세 개의 부등식이 있다. 우리 i는 뒤로 옮겨다니기 때문에 i>a는 고려하지 않는다. 나머지 두 개는 우리가 2차원 행렬을 구성하고 2차원 트리 수조로 dp의 최대치를 유지할 수 있다.
내부 순환 j는 큰 것에서 작은 것으로 해야 한다. 왜냐하면 i>a이기 때문이다.j의 수치가 모두 +1이므로 트리 그룹이 0 값을 업데이트하지 않도록 주의하십시오.
#include
using namespace std;
typedef long long ll;
const int N=1e4+10;
const int M=5e2+10;
int n, K;
int dp[N][M];
int s[N][M];
int h[N];
void upd(int x, int y, int v){
for(;x0; x-=x&-x)
for(int t=y; t>0; t-=t&-t)
ret=max(s[x][t], ret);
return ret;
}
int main(){
scanf("%d%d", &n, &K);
for(int i=1; i<=n; i++)
scanf("%d", h+i);
int ans=0;
for(int i=1; i<=n; i++){
for(int j=K+1; j>=1; j--){
dp[i][j]=sum(h[i]+j, j)+1;
ans=max(ans, dp[i][j]);
upd(h[i]+j, j, dp[i][j]);
}
}
printf("%d
", ans);
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【경쟁 프로 전형적인 90문】008의 해설(python)의 해설 기사입니다. 해설의 이미지를 봐도 모르는 (이해력이 부족한) 것이 많이 있었으므로, 나중에 다시 풀었을 때에 확인할 수 있도록 정리했습니다. ※순차적으로, 모든 문제의 해설 기사를 들어갈 예정입니다. 문자열...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
