uva 10237 - Bishops(dp)

5885 단어
제목 링크: uva 10237 - Bishops
제목 대의: n과 k를 제시하고 nn의 바둑판에 k개의 주교가 서로 공격하지 않으면 몇 가지 방법이 있느냐고 묻는다. 주교의 공격 방식은 사선이다.
문제풀이 사고방식: 바둑판을 45도 회전시킨 다음에 흑백 칸을 서로 분리한다. 왜냐하면 국제적으로 흑격의 주교는 영원히 백격을 공격할 수 없는 주교이기 때문이다.그래서 흑백 칸을 분리해서 생각해 보세요.그리고 한 칸의 색깔에 대해 말하자면 이것은 바둑판에 차를 놓는 것과 유사하다. dp[i][j]는 i행이 j차를 놓았다는 것을 나타낸다. dp[i]=dp[i-1][j]+(n-j+1)𕓬dp[i-1][j]는 이 문제의 n은 가변적이며 먼저 증가한 후에 감소하지만 괜찮다. 행수를 장단순으로 처리하면 결과에 영향을 주지 않는다.마지막으로 덧셈 원리로 흑격에 있는 주교의 수량을 매거하여 더하면 된다.
#include <cstdio>
#include <cstring>

typedef long long ll;
const int N = 40;

int n, k;
ll b[N][N*N], w[N][N*N];

void init () {
    memset(b, 0, sizeof(b));
    memset(w, 0, sizeof(w));
    b[0][0] = w[1][0] = 1;
    for (int i = 1; i <= n; i++) {
        b[i][0] = b[i-1][0];

        int l = (i+1)/2 * 2 - 1;
        for (int j = 1; j <= l && j <= k; j++)
            b[i][j] = b[i-1][j] + (ll)(l-j+1) * b[i-1][j-1];
    }

    for (int i = 2; i <= n; i++) {
        w[i][0] = w[i-1][0];

        int l = i/2 * 2;
        for (int j = 1; j <= l && j <= k; j++)
            w[i][j] = w[i-1][j] + (ll)(l-j+1) * w[i-1][j-1];
    }
}

int main () {
    while (scanf("%d%d", &n, &k) == 2 && n + k) {
        init();

        ll ans = 0;
        for (int i = 0; i <= k; i++)
            ans = ans + b[n][i] * w[n][k-i];
        printf("%lld
", ans);
    }
    return 0;
}
수시로 대기하는 악몽?달리기 수첩은 네가 깨어나는 것을 도울 수 있다.
[Scrapbox] Usercss의 예제 노트

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

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