소와 수조(dp의 최적화)
10243 단어 DP
소는 이런 수조를 좋아한다. 1: 길이가 n2: 모든 수는 1에서 k 사이에 있다. 3: 임의로 연속된 두 수의 A, B, A<=B와 (A% B!=0) 두 조건은 적어도 하나가 성립된다.
조건을 충족시키는 수조가 모두 얼마나 되는지 물어보세요.
설명 입력:
정수 n, k 1 ≤ n ≤ 10 1 ≤ k ≤100000 입력
출력 설명:
정수 내보내기
---------------------------------------------------------------------------------------------------------------------------
이 문제는 dp로 해결할 수 있다. dp[i][j]는 현재 i개의 숫자를 선택했고 현재 숫자가 j일 때의 방안 수를 나타낸다. dp[i][j]의 출처는 dp[i-1][x] 즉 dp[i-1]의 모든 값이다. 반복적으로 구하고 덧붙여야 한다. 임의로 연속된 두 개의 숫자 A, B, A<=B와 (A%B!=0)의 성립 여부를 판단해야 한다. 이유는 dp[i][j]의 값이 앞의 숫자로 확정해야 하기 때문이다.조건이 충족되지 않으면 더할 수 없다.요점은 이렇게 쓰면 세 개의 순환이 필요하고 TLE가 가능하며 dp에 대한 최적화가 필요하다는 것이다.문제를 분석한 결과 제목의 제약 조건의 진실한 의미는 A가 B의 여분의 1의 배수가 될 수 없다는 것이다. 원순환을 분석한 결과 각 dp[i][j]가 덧붙인 것은 상층의 합이기 때문에 먼저 화합을 구하고 하나하나를 덧붙일 수 없다. 그러나 여분의 1의 정수 배의 그 값을 덧붙일 수 없기 때문에 먼저 덧붙인 다음에 모든 값을 빼면 된다.(ps: 내 코드에 적힌 상태 전이 방정식은 문제풀이와 일치하는 것이 아니다. 코드에 적힌 전이 방정식은 자신이 쓴 DFS에서 나온다. 이 전이 방정식도 맞지만 전이 방정식이 다르고 초기화 대상이 다르다는 것을 주의해야 한다)
#include이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 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에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
