체스 중국 장기 dp

4808 단어 【OJ】BZOJdp
표제 면
제목 전송 문
해법
dp 상태의 최적화
  • 가장 폭력 적 인 방법 은 모든 위치 에 포 가 있 는 지 를 매 거 진 다음 에 마지막 으로 폭력 검 사 를 하 는 것 이다
    • .
  • 분명 한 것 은 n, m ≤ 100 n, m ≤ 100 의 데이터 규 모 는 바람 직 하지 않다
    • .
  • 그러면 우 리 는 dp 를 진행 하고 fi, j f i, j 는 i 행 까지 모든 열 에서 포 를 쏘 는 수량 상황 이 j j 의 방안 수 이 고 j j 는 m m 비트 3 진수 이 며 이동 할 때 어느 열 이나 어느 두 열 에서 포 를 쏘 면 된다
    • .
  • 그러나 이 상태 수 는 O (3mn) O (3m n) 로 받 아들 일 수 없다
  • 상 태 를 어떻게 최적화 할 것 인 가 를 고려 해 보면 우 리 는 각 열 에 포 를 쏘 는 상황 이 도대체 어떤 모습 인지 알 필요 가 없다. 우 리 는 몇 열 에 0 / 1 / 2 0 / 1 / 2 개의 포 를 쏘 았 는 지 만 알 고 방안 을 계산 할 때 조합 수
    • 를 사용 할 수 있다.
  • 그러면 우 리 는 상태 fi, j, k f i, j, k 는 i 행 까지 j j 열 이 1 개의 포 를 쏘 았 고 k 열 이 2 개의 포 를 쏘 는 방안 수 를 얻 을 수 있다. 0 은 j, k j, k 를 통 해 직접 계산 할 수 있다
    • .
  • 그렇다면 i + 1 i + 1 줄 에 몇 개의 포 를 쏘 았 는 지 상황 에 따라 대응 하 는 토론 을 해 보 자. 이 부분 은 비교적 간단 하 다
  • 그리고 이렇게 시작 하 자마자 지수 급 의 상 압 dp 가 크게 최적화 되 었 다
  • 시간 복잡 도: O (nm2) O (n m 2)
    • 코드
    #include 
#define int long long
#define Mod 9999973
#define N 110
using namespace std;
template <typename node> void read(node &x) {
    x = 0; int f = 1; char c = getchar();
    while (!isdigit(c)) {if (c == '-') f = -1; c = getchar();}
    while (isdigit(c)) x = x * 10 + c - '0', c = getchar(); x *= f;
}
int n, m, vis[N][N][N], f[N][N][N];
int C(int x) {return x * (x - 1) / 2;}
int dp(int i, int j, int k) {
    if (j < 0 || k < 0) return 0;
    if (i == 0) return (j == 0 && k == 0);
    if (vis[i][j][k]) return f[i][j][k];
    int ret = dp(i - 1, j, k); vis[i][j][k] = 1;
    ret = (ret + dp(i - 1, j - 2, k) * C(m - j - k + 2) % Mod) % Mod;
    ret = (ret + dp(i - 1, j + 2, k - 2) * C(j + 2) % Mod) % Mod;
    ret = (ret + dp(i - 1, j, k - 1) * j % Mod * (m - j - k + 1) % Mod) % Mod;
    ret = (ret + dp(i - 1, j - 1, k) * (m - j - k + 1) % Mod) % Mod;
    ret = (ret + dp(i - 1, j + 1, k - 1) * (j + 1) % Mod) % Mod;
    return f[i][j][k] = ret;
}
main() {
    read(n), read(m);
    int ans = 0;
    for (int i = 0; i <= m; i++)
        for (int j = 0; i + j <= m; j++)
            ans = (ans + dp(n, i, j)) % Mod;
    cout << ans << "
    "    ;
    return 0;
}
    C++ 클래스에서this 포인터 설명
    Spark 사례 실습

    좋은 웹페이지 즐겨찾기

    개발자 우수 사이트 수집

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