BZOJ4806포
Description D e s c r i p t i o n
전송문
n∗mn∗m의 바둑판이 있는데 바둑판 위에 포를 놓고 포와 포 사이에 서로 공격하지 않는 방안의 수를 묻는다.
Solution S o l u t i o n
딱 봐도 DP야.
n, m n을 보면 m은 상압 DP의 데이터 규모에 비해 비교적 크기 때문에 상압이 좋지 않다.
자세하게 분석하면 포와 포 사이에 충돌이 발생하고 소재한 줄이나 열에만 33개 이상의 포가 있다.
그리고 한 열의 포 수가 33개보다 적으면 이 두 열이 어느 위치에 있든 서로 공격하지 않는다.따라서 우리는 이 몇 개의 포의 구체적인 배치 위치를 기록할 필요가 없다. 포가 11개나 22개 놓여 있는 위치만 알면 된다. 이렇게 하면 포의 열 수가 없어도 내놓을 수 있다.
따라서 우리는 d(i, j, k)d(i, j, k)로 앞의 i행에 jj열이 11개의 포를 놓았고, k열이 22개의 포를 놓았다는 것을 나타낸다.
ii행에서 최대 두 개의 포를 놓을 수 있기 때문에 상황에 따라 상태 이동 방정식을 작성한다(상태 이동 계산은 모두 모형을 추출하는 의미에서 진행한다)
상태 이동 방정식이 좀 많아서 세심해야 합니다.
그리고 이 상태 이동 방정식을 살펴보면 이전의 상태와만 관련이 있다는 것을 발견하고 우리는 스크롤 그룹으로 공간을 최적화할 수 있다.
Code C o d e
#include
", ans);
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에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
