K 상승단. K 상승단. K 상승단.

제목.

자연수 1... n의 배열 A[1... N]는 몇 개의 단조로운 증가 서열로 나눌 수 있다.각 단조로운 증가 시퀀스는 연속 요소 A[st...ed]로 구성되며 다음 조건을 충족합니다. 1 < = s t, e d < = n;1<=st,ed<=n; 1<=st,ed<=n; A [ i ] < A [ i + 1 ] ( s t < = i < = e d − 1 ) A[i] A[i]<A[i+1](st<=i<=ed−1) e d = n 또는 A [e d] > A [e d + 1] ed=n 또는 A [ed] > A [ed+1] ed=n 또는 A [ed] > A [ed+1] 예: 배열 1 2 4 5 6 3 9 10 7 8 3개의 단조로운 증가 서열 1 2 3 4 5 6으로 나눌 수 있다.3 9 10 ;7 8 ; 그래서 우리는 이것이 3상승단 서열이라고 부른다.현재 n과 k를 정하고 n의 전체 배열 중의 k 상승 단계 서열의 개수를 구합니다.

입력

입력은 n, k (1 < n < 20, 1 < k < n) 수를 포함하는 행만 1행으로 구성됩니다.

출력

n의 모든 k 상승 단계의 개수를 출력합니다.

샘플 가져오기

K.IN
3 2

출력 예제

K.OUT
4

설명

(설명, 적합 배열은 13231213231)

문제풀이의 방향

이 문제는 DP DP DP로 f[i, j] f[i, j] f[i, j] f[i, j]를 1i1~i 1i분에서 jj 세그먼트에 맞는 정렬 개수 F[i] [j] = (i-j+1) f [i-1] [j-1] + j-f [i-1] [j]를 설정합니다.( i < = n , j < n ) F[i][j]=(i-j+1)*f[i-1][j-1]+j*f[i-1][j];(i<=n,jF[i][j]=(i−j+1)∗f[i−1][j−1]+j∗f[i−1][j];(i<=n,j그 중에서 i는 i의 전체 배열을 나타내고 j는 구분된 단수를 나타낸다

절차는 다음과 같다.

#include
#include
#include 
#include

using namespace std;

int n,k;

long long f[2001][2001];

int main()
{
	scanf("%d%d", &n, &k);
	for(int i = 1; i <= n; ++i)
	for(int j = 1; j <= k; ++j)
	if(i == j) f[i][j] = 1;
	else f[i][j] = j * f[i - 1][j] + (i - j + 1) * f[i - 1][j - 1];
	printf("%lld", f[n][k]);
	return 0;
}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

[BOJ]11048(python)

python 풀이 DP를 이용해 풀이 보통 이런 문제는 dfs나 bfs로 풀이하는 것이여서 고민을 했는데 이 문구 덕분에 DP 를 이용해 풀이할 수 있었다 뒤로 돌아가는 등의 경우를 고려하지 않아도 되기 때문이다 코...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

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