소 손님 드 롭 Voicing LIS

6074 단어 DP알고리즘동적 계획
제목 링크
제목 분석:
제목 은 문자열 을 정 했 습 니 다. 모두 두 개의 작업 을 수행 할 수 있 고 Drop - 2 만 비용 이 듭 니 다.이것 은 바로 우리 가 꼬치 를 주기 적 인 1 - n 으로 바 꾸 면 된다 는 것 이다 (예 를 들 어 k - n 1 - (k - 1).연속 적 인 여러 개의 Drop - 2 조작 은 하나의 비용 만 들 면 하나의 조작 이 라 고 볼 수 있다.이제 우 리 는 문자열 의 임의의 위치 에 대해 Drop - 2 작업 을 할 수 있 습 니 다. (Invert 작업 을 통 해 임의의 위 치 를 꼴찌 로 바 꿀 수 있 기 때 문 입 니 다) 그리고 우 리 는 길이 가 K 인 연속 문자열 에 대해 Drop - 2 작업 을 한 후에 이 문자열 은 사실은 오른쪽으로 한 자 리 를 이동 한 것 을 발견 할 수 있 습 니 다.거꾸로 보면 이 문자열 의 오른쪽 첫 번 째 요소 가 k 단 위 를 왼쪽으로 옮 긴 것 으로 볼 수 있다.(k 는 임의로 선택 할 수 있 습 니 다) 지금 우 리 는 문 제 를 바 꾸 었 습 니 다. 매번 한 숫자 를 임의의 위치 로 이동 할 수 있 습 니 다. 최소 이동 횟수 를 구하 여 이 꼬치 를 k - n 1 - (k - 1) 형식 으로 바 꿀 수 있 습 니 다.이동 횟수 를 최소 화 하려 면 원래 의 배열 을 충분히 이용 해 야 한다 고 생각 하기 쉽다. 그 중에서 우리 에 게 유리 한 것 은 바로 질서 있 는 하위 배열 이다. 그러면 문 제 를 최 장 상승 하위 서열 (LIS) 을 구 하 는 문제 로 만 들 었 다.
AC 코드:
#include
#include
using namespace std;
const int MAX_N = 505,INF=1e9;
int dp[MAX_N],arr[MAX_N];
//                               ，
//                     ，        。
int main()
{
	int n;
	cin >> n;
	for (int i = 0; i < n; i++)cin >> arr[i];
	int length = 0;//      
	for (int cnt = 0; cnt < n; cnt++)//cnt      
	{
		fill(dp, dp + MAX_N, INF);
		for (int i = cnt; i < n+cnt; i++)
			*lower_bound(dp, dp + MAX_N, arr[i%n]) = arr[i%n];
		length = max(length, (int)(lower_bound(dp, dp + MAX_N, INF) - dp));
	}
	cout << n - length;
	return 0;
}
3. 뉴턴 교체 법 은 방정식 의 뿌리 를 구한다.
[LeetCode - 알고리즘] 64. 최소 경로 와 (자바 구현)

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage