dp-도전 프로그램 설계 경연 - 상태의 선택 다중 부분 및 LIS

DP의 핵심은 상태의 정의, 상태의 교묘한 정의이다.
다중 부분 및
제목:정수 a1,a2,......an, 종류마다 m개씩, 그 중에서 몇 개의 수를 선택하여 그것들의 합이 K가 될 수 있는지 판단한다.
분석: 완전 가방이 꽉 찬 문제입니다. 당연히 O(NKmi)를 사용할 수 있습니다.
그러나 상태 dp[i][j]를 i번째 숫자로 정의하여 j의 나머지 개수를
이렇게 하면 dp[i][j]>=0이면 j와 전 i개수로 채울 수 있다. 그렇지 않으면 우리는 dp[i][j]=-1을 정의한다.
그래서 세 가지 상태 이동 방식이 있어요.
if(dp[i-1][j]>=0) dp[i][j]=mi;(모두 남았다)
else if(a[i]>j || dp[i][j-a[i]]<=0) dp[i][j]=-1;(채우지 못함)
else a[i][j]=a[i][j-a[i]]-1; (채울 수 있고, 남은 수는 a[i][j-a[i]]보다 1)
이 방식은 마치 완전한 배낭과 같아서 하나하나 뒤로 밀어 내부 순환을 줄이고 복잡도도 O(NK)이다.
코드는 다음과 같다.
4

int dp[maxn];
fill(dp,dp+n,-1)
for(int i=1;i<=n;i++){
	for(int j=1;j<=k;j++){
	if(dp[i-1][j]>=0) dp[i][j]=m[i];
	else if(a[i]>j || dp[i][j-a[i]]<=0) dp[i][j]=-1;
	else dp[i][j]=dp[i][j-a[i]]-1;
	}
}

단조로운 대기열 최적화 방법: O(NK) 시간 내에 무게를 구할 수 있다.
LIS 질문
어떻게 O(nlogn)로 이 문제를 실현합니까?
최장 증가 하위 시퀀스는 Longest Increasing Subsequence 아래에 LIS로 간략하게 기록되어 있습니다.정렬 + LCS 알고리즘 및 DP 알고리즘은 무시했습니다. 이 두 가지는 너무 이해하기 쉽습니다.
만약 서열 d[1.9] = 2 1 5 3 6 4 8 9 7이 존재한다면 LIS 길이가 5인 것을 알 수 있다.n 다음에 한 걸음 한 걸음 그것을 찾아내 보세요.우리는 서열 B를 정의한 다음에 i = 1 to 9로 하여금 이 서열을 하나하나 고찰하게 한다.그 밖에 우리는 하나의 변수로 현재 가장 긴 계산이 얼마나 되었는지 기록한다
먼저 d[1]를 B에 질서정연하게 넣고 B[1]=2를 명령한다. 즉, 하나의 숫자 2만 있을 때 길이가 1인 LIS의 최소 끝은 2이다.이때 Len=1
그리고 d[2]를 질서정연하게 B에 넣고 B[1]=1을 시키면 길이가 1인 LIS의 가장 작은 끝은 1이고 d[1]=2는 이미 쓸모가 없어서 이해하기 쉽죠.이때 Len=1
이어 d[3]=5, d[3]>B[1]이므로 B[1+1]=B[2]=d[3]=5, 즉 길이가 2인 LIS의 최소 끝이 5라는 것은 이해하기 쉽죠.이때B[1.2]=1,5,Len=2
다시, d[4]=3, 1,5사이에 딱 들어가기 때문에 1의 위치는 분명히 적합하지 않다. 왜냐하면 1은 3보다 작고 길이가 1인 LIS의 최소 끝은 1이어야 하기 때문이다. 이렇게 하면 길이가 2인 LIS의 최소 끝은 3이기 때문에 5를 탈락시킬 수 있다. 이때 B[1.2]=1, 3, Len=2
계속, d[5]=6, 그것은 3 뒤에 있다. B[2]=3, 6은 3 뒤에 있기 때문에 B[3]=6을 쉽게 추측할 수 있다. 이때 B[1.3]=1, 3, 6은 쉽게 이해할 수 있겠지?Len = 3이야.
여섯 번째, d[6]=4, 네가 보기에 그것은 3과 6 사이에 있다. 그래서 우리는 6을 교체하고 B[3]=4를 얻을 수 있다.B[1.3] = 1, 3, 4, 렌 계속 3
일곱 번째, d[7]=8, 그것은 매우 크고 4보다 크다, 응.그래서 B[4]=8.렌이 4가 됐어요.
8번째, d[8]=9, B[5]=9를 획득, 응.Len은 계속 커졌다. 5가 되었다.
마지막, d[9]=7, B[3]=4와 B[4]=8 사이에 있기 때문에 우리는 최신 B[4]=7, B[1.5]=1, 3, 4, 7, 9, Len=5를 알고 있다.
그래서 우리는 LIS의 길이가 5라는 것을 알게 되었다.
!!!!! 주의하다.이 1, 3, 4, 7, 9는 LIS가 아니라 저장된 대응하는 길이의 LIS의 최소 끝일 뿐이다.이 끝이 있으면 우리는 하나하나 데이터를 삽입할 수 있다.마지막 d[9]=7이 업데이트되는 것은 이 그룹의 데이터에 아무런 의미가 없지만 뒤에 두 개의 숫자 8과 9가 나오면 8을 d[5], 9를 d[6]로 업데이트할 수 있고 LIS의 길이는 6이다.
B에 데이터를 삽입하는 것은 질서정연하고 교체를 진행하기 때문에 옮길 필요가 없다. 즉, 우리는 이분 검색을 사용하여 모든 숫자의 삽입 시간을 O(logN)~~~~~~로 최적화할 수 있다. 그래서 알고리즘의 시간 복잡도는 O(NlogN)~로 낮아졌다!
개인 이해: 이 업데이트의 역할은 무엇입니까?현재의 업데이트는 뒤의 수가 더 긴 점증자 서열을 생성하기 위한 것이다. dp[i]가 작아지기 때문에 뒤의 서열이 더 길어질 수 있고 매번 업데이트는 이전의 상태에 영향을 주지 않는다.
4

fill(dp,do+n,INF);
for(int i=0;i<n;i++){
	<span style="color:#ff0000;">*</span>lower_bound(dp,dp+n,a[i])=a[i];
}
cout<<lower_bound(dp,dp+n,INF)-dp<<endl;

주의lowerbound 및 upperbound는 표준 라이브러리 함수,lowerbound(a,a+n,k)에서 찾은 것은 a[i]>=k의 가장 작은 것이다
포인터(배열)
함수 lowerbound () 는first와last의 전폐후 개방 구간에서 2분 검색을 하고 val보다 크거나 같은 첫 번째 요소의 위치를 되돌려줍니다.모든 원소가 val보다 작으면last의 위치를 되돌려주고 원소를 찾는 첫 번째 삽입 가능한 위치, 즉'원소값>=찾기값'의 첫 번째 원소의 위치를 되돌려줍니다.
upper_bound (const key type & key): 원소를 찾을 수 있는 마지막 삽입 가능한 위치, 즉 '원소 값 > 찾기 값' 의 첫 번째 원소의 위치를 되돌려줍니다.