棋盘上的車

zerol edited 1 年,1 月前

title: 【题解】EOJ - 棋盘上的車 (bzoj 2616 - SPOJ PERIODNI)
date: 2017-12-07 22:37:30
categories: ACM
tags:
- dp


题目

http://acm.ecnu.edu.cn/problem/3438/

题意

给定一个由 n 条高度不等的列组成的棋盘,其中所有列的底边位于同一水平线上。求放置 k 个互不攻击的車的方案总数。(車能互相攻击当且仅当能通过棋盘上连续的一行或一列格子直接连在一起)

题解

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define FOR(i, x, y) for (decay<decltype(y)>::type i = (x), _##i = (y); i < _##i; ++i)
#define FORD(i, x, y) for (decay<decltype(x)>::type i = (x), _##i = (y); i > _##i; --i)
#ifdef zerol
#define dbg(args...) do { cout << "\033[32;1m" << #args<< " -> "; err(args); } while (0)
#else
#define dbg(...)
#endif
void err() { cout << "\033[39;0m" << endl; }
template<typename T, typename... Args>
void err(T a, Args... args) { cout << a << ' '; err(args...); }
// -----------------------------------------------------------------------------
const LL maxn = 5E2 + 100, MOD = 1E9 + 7, M = 1E6 + 10;
LL h[maxn], f[maxn][maxn], g[maxn];

inline void up(LL& a, LL b) { (a += b) %= MOD; }

LL pown(LL x, LL n, LL MOD) {
    LL ret = MOD != 1;
    for (x %= MOD; n; n >>= 1, x = x * x % MOD)
        if (n & 1) ret = ret * x % MOD;
    return ret;
}

LL invf[M], fac[M];
void fac_inv_init(LL n, LL p) {
    fac[0] = 1;
    FOR (i, 1, n)
        fac[i] = i * fac[i - 1] % p;
    invf[n - 1] = pown(fac[n - 1], p - 2, p);
    FORD (i, n - 2, -1)
        invf[i] = invf[i + 1] * (i + 1) % p;
}

inline LL C(LL n, LL m) { // m >= n >= 0
    return m < n || n < 0 ? 0 : fac[m] * invf[n] % MOD * invf[m - n] % MOD;
}

LL go(LL l, LL r, LL d) {
    if (l > r) return 0; // trick!
    LL k = r;
    FOR (i, l, r)
        if (h[i] < h[k]) k = i;
    LL len = r - l + 1, height = h[k] - d;
    LL a = go(l, k - 1, h[k]), b = go(k + 1, r, h[k]);
    fill(g, g + len + 1, 0);
    FOR (i, 0, k - l + 1)  // (k - 1) - l + 1
        FOR (j, 0, r - k + 1) // r - (k + 1) + 1
            up(g[i + j], f[a][i] * f[b][j]);
    FOR (i, 0, len + 1)
        FOR (t, 0, i + 1)
             up(f[k][i], g[i - t] * C(t, len - (i - t)) % MOD * C(t, height) % MOD * fac[t]);
    return k;
}

int main() {
#ifdef zerol
    freopen("in", "r", stdin);
#endif
    fac_inv_init(M, MOD);
    int n, k;
    cin >> n >> k;
    FOR (i, 1, n + 1) cin >> h[i];
    f[0][0] = 1; // trick!
    cout << f[go(1, n, 0)][k] << endl;
}

Comments

DingJR

状态转移方程的length应该是length-k+i吧

zerol

多谢指出,确实写错了。

qiuzhipeng

include

using namespace std;
typedef long long LL;

define FOR(i, x, y) for (decay::type i = (x), ##i = (y); i < ##i; ++i)

define FORD(i, x, y) for (decay::type i = (x), ##i = (y); i > ##i; –i)

ifdef zerol

define dbg(args…) do { cout << “\033[32;1m” << #args<< ” -> “; err(args); } while (0)

else

define dbg(…)

endif

void err() { cout << “\033[39;0m” << endl; }
template
void err(T a, Args… args) { cout << a << ‘ ‘; err(args…); }
// -----------------------------------------------------------------------------
const LL maxn = 5E2 + 100, MOD = 1E9 + 7, M = 1E6 + 10;
LL h[maxn], f[maxn][maxn], g[maxn];

inline void up(LL& a, LL b) { (a += b) %= MOD; }

LL pown(LL x, LL n, LL MOD) {
LL ret = MOD != 1;
for (x %= MOD; n; n >>= 1, x = x * x % MOD)
if (n & 1) ret = ret * x % MOD;
return ret;
}

LL invf[M], fac[M];
void fac_inv_init(LL n, LL p) {
fac[0] = 1;
FOR (i, 1, n)
fac[i] = i * fac[i - 1] % p;
invf[n - 1] = pown(fac[n - 1], p - 2, p);
FORD (i, n - 2, -1)
invf[i] = invf[i + 1] * (i + 1) % p;
}

inline LL C(LL n, LL m) { // m >= n >= 0
return m < n || n < 0 ? 0 : fac[m] * invf[n] % MOD * invf[m - n] % MOD;
}

LL go(LL l, LL r, LL d) {
if (l > r) return 0; // trick!
LL k = r;
FOR (i, l, r)
if (h[i] < h[k]) k = i;
LL len = r - l + 1, height = h[k] - d;
LL a = go(l, k - 1, h[k]), b = go(k + 1, r, h[k]);
fill(g, g + len + 1, 0);
FOR (i, 0, k - l + 1) // (k - 1) - l + 1
FOR (j, 0, r - k + 1) // r - (k + 1) + 1
up(g[i + j], f[a][i] * f[b][j]);
FOR (i, 0, len + 1)
FOR (t, 0, i + 1)
up(f[k][i], g[i - t] * C(t, len - (i - t)) % MOD * C(t, height) % MOD * fac[t]);
return k;
}

int main() {

ifdef zerol

freopen("in", "r", stdin);

endif

fac_inv_init(M, MOD);
int n, k;
cin &gt;&gt; n &gt;&gt; k;
FOR (i, 1, n + 1) cin &gt;&gt; h[i];
f[0][0] = 1; // trick!
cout &lt;&lt; f[go(1, n, 0)][k] &lt;&lt; endl;

}

你正在回复博客
存在问题!