动态规划 – hahaschool

Codeforces 666C Codewords

October 12, 20162016-10-12hahaschoolLeave a comment

题意

已知一个字符串 $s$ ，有 $m$ 个询问需要你回答。

对于每个询问，有两种可能性：

1型：给你另外一个字符串 $s'$ ，然后令 $s = s'$ 。（即用新串更新当前的 $s$ ）
2型：给你一个整数 $n$ ，你要回答：可以构造多少种不同的长度为 $n$ 的字符串 $p$ ，使得字符串 $s$ 是字符串 $p$ 的一个子序列，只考虑英文小写字母.

进一步解释：

子序列：假如有一个字符串 $a$ ，我们去掉其中的一些字母（只能“去掉”，而不能交换字母的位置），得到另外一个串 $b$ ，我们把 $b$ 称为 $a$ 的子序列。
举个例子： $"hhhl"$ 可以是 $"hahaschool"$ 的子序列， $"sik"$ 可以是 $"suika"$ 的子序列。

思路

首先，你需要注意到其实字符串 $s$ 的内容并不重要，影响答案的是字符串 $s$ 的长度。

我们来考虑这样的一种思路：

假设我们构造的串是 $p$ ， $s$ 是 $p$ 的子序列，我们设定： $s$ 在 $p$ 中的出现位置必须是字典序最小的。直白一点的说法： $s$ 是 $p$ 删除一些字母得到的，我们强制删除字母的时候，在连续相同的一段字母中，必须从右往左删。

举两个例子方便理解这种想法：

$s = "hahl" p = "hahaschool"$ ， $"hahl"$ 在 $"hahaschool"$ 中的对应位置必须是1、2、3、10（下标从1开始）。

$s = "abad" p = "aaabbbaaaddd"$ ， $"abad"$ 在 $"aaabbbaaaddd"$ 中的对应位置必须是1、4、7、10（下标从1开始）。

有了这种想法我们就可以把s在固定的p中的对应位置关系唯一地确定下来。同时我们得到了这样的结论：

假设s的每一位在p中对应的位置为 $p_i$ ，字符串s的内容是 $s_i$ ，那么 $s_{k+1}$ 一定不会出现在p的第 $p_k$ 位到 $p_{k+1}-1$ 位，因为如果不这样的话， $s$ 在 $p$ 中的出现位置就不是“字典序最小”的了。

有了这个结论，我们就有了初步的想法，我们首先选择 $s$ 在 $p$ 中的出现位置，这个很简单，就是 $\binom{n}{|s|}$ （其中n是要构造的p的长度，|s|是s的长度），接下来，对于每种s在p中出现位置的分布，在第 $p_{|s|}$ 位之前的未填充空位，都可以填入25种字母（参见我们刚才得到的结论），在之后的空位，都可以任意填入26种字母。

这样，如果我们枚举s在p中出现的最后位置 $p_{|s|}$ （下面用k表示），我们就可以算出答案，使用下面这个式子：

$ans=\sum_{k=|s|}^{n}\binom{k-1}{|s|-1}25^{k-|s|}26^{n-k}$

很显然如果直接拿这个式子出答案是 $O(n^2)$ 的，不满足时间限制，我们要想些办法。

观察一下上面的式子我们可以发现，可以提出 $26^n$ 这一项，这样对于相同的 $|s|$ ，不同的n的询问，我们只需要做一次 $O(n)$ 的计算就可以全数回答。这提醒我们离线处理询问：把所有询问按照|s|为第一基准，n 为第二基准进行排序，依序处理，再按出现顺序排序，依序输出。

这样做是可行的，因为 $|s|$ 最多有 $\sqrt{n}$ 种（考虑极端情况： ${|s|}_1 = 1$ , ${|s|}_2 = 2$ , ${|s|}_3 = 3$ ,…，根据等差数列求和公式，项数最多只能到 $\sqrt{100000}$ ），对于每种不同的 $|s|$ 都要做一个 $O(n)$ 的处理，所以总复杂度为 $O(n\sqrt{n})$ ，符合题目限制。

至此本题圆满解决。

实现

#define REP(i,t) for(int i = 0;i < t; i++)
#define REP_1(i,t) for(int i = 1;i <= t; i++)
#define CASE_LOOP int ___;scanf(" %d",&___);for(int __ = 1; __ <= ___; __++)
#define FOR_EDGE(i,u) for (int i = head[u]; i; i = nxt[i])
#define ADHOC_CIN(typ,name) typ name;cin >> name;

using namespace std;

typedef long long LL;

int n;
string cur;

const int MAXN = 100005, MODER = 1000000007;
LL fac[MAXN],fac_inv[MAXN];
LL fac26[MAXN],fac25[MAXN];
LL fac26_inv[MAXN],fac25_inv[MAXN];
LL get_mod(LL a){
    if(a >= MODER || a < 0) a %= MODER;
    if(a < 0) a += MODER;
    return a;
}

LL mul_mod(LL a,LL b){
    return get_mod(get_mod(a)*get_mod(b));
}

LL pow_mod(LL a,LL p){
    LL ret = 1;
    while (p) {
        if(p&1) ret = mul_mod(ret, a);
        a = mul_mod(a, a);
        p >>= 1;
    }
    return ret;
}

LL sum_mod(LL a,LL b){
    return get_mod(get_mod(a) + get_mod(b));
}

LL inv_mod(LL a){
    return pow_mod(a, MODER-2);
}

void prep(){
    fac[0] = fac_inv[0] = fac26[0] = fac25[0] = fac26_inv[0] = fac25_inv[0] =  1;
    REP_1(i, MAXN-1){
        fac[i] = mul_mod(fac[i-1], i);
        fac_inv[i] = mul_mod(fac_inv[i-1], inv_mod(i));
        fac26[i] = mul_mod(fac26[i-1], 26);
        fac25[i] = mul_mod(fac25[i-1], 25);
        fac26_inv[i] = mul_mod(fac26_inv[i-1], inv_mod(26));
        fac25_inv[i] = mul_mod(fac25_inv[i-1], inv_mod(25));
    }
}

LL C(LL n,LL r){
    return mul_mod(fac[n], mul_mod(fac_inv[r], fac_inv[n-r]));
}

struct Query{
    int id,len,qrn;
    LL res;
} query[MAXN];

bool cmp_qrn(const Query &a,const Query &b){
    if(a.qrn == b.qrn) return a.len < b.len;
    return a.qrn < b.qrn;
}

bool cmp_id(const Query &a,const Query &b){
    return a.id < b.id;
}

int tot = 0;

void solve(){
    sort(query, query+tot, cmp_qrn);
    int cqrn = 0,ccur = 0;
    LL cval = 0;
    REP(i,tot){
        if(query[i].len < query[i].qrn){
            query[i].res = 0;
            continue;
        }
        if(query[i].qrn != cqrn){
            ccur = cqrn = query[i].qrn;
            ccur--;
            cval = 0;
        }
        while(ccur < query[i].len){
            ccur++;
            cval = sum_mod(cval, mul_mod(mul_mod(mul_mod(fac25[ccur], fac25_inv[cqrn]), fac26_inv[ccur]), C(ccur-1,cqrn-1)));
        }
        query[i].res = mul_mod(cval, fac26[query[i].len]);
    }

    sort(query, query+tot, cmp_id);
    REP(i, tot){
        cout << query[i].res << endl;
    }
}

int main(int argc, const char * argv[]){
    prep();
    cin >> n >> cur;
    REP_1(i, n){
        ADHOC_CIN(int, op);
        if(op == 1){
            cin >> cur;
        }else{
            ADHOC_CIN(int, a);
            query[tot] = {tot++,a,(int)cur.size(),0};
        }
    }
    solve();
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

#define REP(i,t) for(int i = 0;i < t; i++)

#define REP_1(i,t) for(int i = 1;i <= t; i++)

#define CASE_LOOP int ___;scanf(" %d",&___);for(int __ = 1; __ <= ___; __++)

#define FOR_EDGE(i,u) for (int i = head[u]; i; i = nxt[i])

#define ADHOC_CIN(typ,name) typ name;cin >> name;

using namespace std;

typedef long long LL;

int n;

string cur;

const int MAXN = 100005, MODER = 1000000007;

LL fac[MAXN],fac_inv[MAXN];

LL fac26[MAXN],fac25[MAXN];

LL fac26_inv[MAXN],fac25_inv[MAXN];

LL get_mod(LL a){

if(a >= MODER || a < 0) a %= MODER;

if(a < 0) a += MODER;

return a;

}

LL mul_mod(LL a,LL b){

return get_mod(get_mod(a)*get_mod(b));

}

LL pow_mod(LL a,LL p){

LL ret = 1;

while (p) {

if(p&1) ret = mul_mod(ret, a);

a = mul_mod(a, a);

p >>= 1;

}

return ret;

}

LL sum_mod(LL a,LL b){

return get_mod(get_mod(a) + get_mod(b));

}

LL inv_mod(LL a){

return pow_mod(a, MODER-2);

}

void prep(){

fac[0] = fac_inv[0] = fac26[0] = fac25[0] = fac26_inv[0] = fac25_inv[0] = 1;

REP_1(i, MAXN-1){

fac[i] = mul_mod(fac[i-1], i);

fac_inv[i] = mul_mod(fac_inv[i-1], inv_mod(i));

fac26[i] = mul_mod(fac26[i-1], 26);

fac25[i] = mul_mod(fac25[i-1], 25);

fac26_inv[i] = mul_mod(fac26_inv[i-1], inv_mod(26));

fac25_inv[i] = mul_mod(fac25_inv[i-1], inv_mod(25));

}

LL C(LL n,LL r){

return mul_mod(fac[n], mul_mod(fac_inv[r], fac_inv[n-r]));

}

struct Query{

int id,len,qrn;

LL res;

} query[MAXN];

bool cmp_qrn(const Query &a,const Query &b){

if(a.qrn == b.qrn) return a.len < b.len;

return a.qrn < b.qrn;

}

bool cmp_id(const Query &a,const Query &b){

return a.id < b.id;

}

int tot = 0;

void solve(){

sort(query, query+tot, cmp_qrn);

int cqrn = 0,ccur = 0;

LL cval = 0;

REP(i,tot){

if(query[i].len < query[i].qrn){

query[i].res = 0;

continue;

}

if(query[i].qrn != cqrn){

ccur = cqrn = query[i].qrn;

ccur--;

cval = 0;

}

while(ccur < query[i].len){

ccur++;

cval = sum_mod(cval, mul_mod(mul_mod(mul_mod(fac25[ccur], fac25_inv[cqrn]), fac26_inv[ccur]), C(ccur-1,cqrn-1)));

}

query[i].res = mul_mod(cval, fac26[query[i].len]);

}

sort(query, query+tot, cmp_id);

REP(i, tot){

cout << query[i].res << endl;

}

int main(int argc, const char * argv[]){

prep();

cin >> n >> cur;

REP_1(i, n){

ADHOC_CIN(int, op);

if(op == 1){

cin >> cur;

}else{

ADHOC_CIN(int, a);

query[tot] = {tot++,a,(int)cur.size(),0};

}

solve();

return 0;

}

Codeforces 295D Greg and Caves

October 12, 20162018-04-07hahaschoolLeave a comment

题意

你有一个 $n*m$ 大小的棋盘， $n$ 行， $m$ 列，行号列号都从 $1$ 开始，行从上到下数到 $n$ ，列从左到右数到 $m$ ，棋盘的每一个格子可以是黑色或者白色。

当满足全部下述条件的时候，认为棋盘上出现了一个”Cave“：

存在一个线段 $[l,r] (1 <= l <= r <= n)$ ，使得 $l,l+1,l+2,...,r$ 这些行都有且仅有两个黑色格子，其他行不存在黑色格子。
存在一个行号，使得：
- 对于任意存在黑色格子的行 $r$ ，把这行的黑色格子对应的列号和黑色格子之间的列号加入一个集合，称之为 $S(r)$ 。
- 任取t及t之上的两个有黑色格子的行，令上方的行为 $u$ ，下方的行 $d$ ，则 $S(u)$ 是 $S(d)$ 的子集。
- 任取 $t$ 及 $t$ 之下的两个有黑色格子的行，令上方的行为 $u$ ，下方的行为 $d$ ，则 $S(d)$ 是 $S(u)$ 的子集。

你要输出有多少染色的方案，使得棋盘出现一个“Cave”，答案模 $1000000007$ 。

思路

翻译一下题意，就是让我们找一种染色方案，让棋盘上出现下面这样的图案（下图中 $n = m = 5 ,l = 3, r = 15, t = 8$ ）。

295D

可以发现，这个图案可以以t行为界分拆为上下两个部分，不妨令 $hf[h][w]$ 表示得到高度为h的，底部两个黑块宽度必须为w的，每一行都有黑块的，半个图案的染色方案数。

我们可以很容易发现如下的递推关系：

$hf[h][w] = {hf[h-1][w] + 2\times hf[h-1][w-1] + 3\times hf[h-1][w-2] +4\times hf[h-1][w-3] + ... + w\times hf[h-1][1]}$

即：

$hf[h][w] = \sum_{k=1}^{w} k\cdot hf[h-1][w+1-k]$

考虑同一高度的相邻两项之差：

$hf[h][w] - hf[h][w-1] = \sum_{k=1}^{w} hf[h-1][k]$

这样，我们一行行地计算 $hf$ 的值，一边维护每一行的前缀和，一边算下一项，这样可以用 $O(n^2)$ 的时间完成预处理。

接下来我们考虑如何把两个一半的图案合成一个，我们令 $al[h][w]$ 表示得到高度为 $h$ ，最宽处宽度为 $w$ ，每一行都有黑块的图案的染色方案数，我们有：

$al[h][w] =\sum \left\{\begin{matrix} {hf[1][w] \cdot (2\times hf[h-1][w-1] + 3\times hf[h-1][w-2] + 4\times hf[h-1][w-3] + ... + w\times hf[h-1][1])} \\ {hf[2][w] \cdot (2\times hf[h-2][w-1] + 3\times hf[h-2][w-2] + 4\times hf[h-2][w-3] + ... + w\times hf[h-2][1])} \\ {hf[3][w] \cdot (2\times hf[h-3][w-1] + 3\times hf[h-3][w-2] + 4\times hf[h-3][w-3] + ... + w\times hf[h-3][1])} \\ ... \\ {hf[h][w] \cdot (2\times hf[0][w-1] + 3\times hf[0][w-2] + 4\times hf[0][w-3] + ... + w\times hf[0][1])} \end{matrix}\right.$

即：

$al[h][w] = \sum \left\{\begin{matrix} hf[1][w]\times \sum_{k=1}^{w-1} (k+1)\cdot hf[h-1][w-k] \\ hf[2][w]\times \sum_{k=1}^{w-1} (k+1)\cdot hf[h-2][w-k] \\ hf[3][w]\times \sum_{k=1}^{w-1} (k+1)\cdot hf[h-3][w-k] \\ ... \\ hf[h][w]\times \sum_{k=1}^{w-1} (k+1)\cdot hf[0][w-k] \end{matrix}\right.$

为了让式子更简洁，我们令 $rc[h][w] = \sum_{k=1}^{w-1} (k+1)\cdot hf[h][w-k]$ ，这样的话，我们就有：

$al[h][w] = \sum_{k=1}^{h} hf[k][w]\cdot rc[h-k][w]$

很明显这个式子是一个卷积，如果我们可以预处理出 $rc$ 的值，就可以使用FFT进行快速运算。我们发现 $rc$ 的递推关系和 $hf$ 的递推关系非常相似，我们依然考虑同行相邻两项的差值：

$rc[h][w] - rc[h][w-1] = hf[h][w-1] + \sum_{k=1}^{w-1} hf[h][w-k]$

这样我们依然采用一边计算一边维护前缀和的方法，可以在 $O(n^2)$ 的时间完成 $rc$ 的预处理。

预处理好 $rc$ 之后，就是计算卷积了，因为题目要求模 $1000000007$ ，我们需要采用NTT+CRT的方式实现任意模空间下的卷积（具体实现原理不是我们的讨论范围），这样的话，在最恶劣情况，我们需要做18000次4096点NTT，单次NTT耗时几毫秒，超时无法避免，我们只能考虑进一步优化。

我们继续考虑，令 $dw[w]$ 表示最宽处宽度为 $w$ ，高度范围在 $1 \sim N$ 的图案，有多少方案可以作成，那么我们有：

$dw[w] = \sum \left\{\begin{matrix} N\cdot al[1][w] \\ (N-1)\cdot al[2][w] \\ (N-2)\cdot al[3][w] \\ ... \\ 1 \cdot al[N][w] \end{matrix}\right.$

把 $al$ 打开，就有：

$dw[w] = \sum \left\{\begin{matrix} N\times hf[1][w]\cdot rc[0][w] \\ (N-1)\times (hf[1][w]\cdot rc[1][w] + hf[2][w]\cdot rc[0][w]) \\ (N-2)\times (hf[1][w]\cdot rc[2][w] + hf[2][w]\cdot rc[1][w] + hf[3][w]\cdot rc[0][w]) \\ ... \\ 1\times (hf[1][w]\cdot rc[N-1][w] + hf[2][w]\cdot rc[N-2][w] + ... + hf[N][w]\cdot rc[0][w]) \end{matrix}\right.$

我们把 $dw[w]$ 重新整理一下：

$dw[w] = \sum \left\{\begin{matrix} hf[1][w]\times (N\cdot rc[0][w] + (N-1)\cdot rc[1][w] + (N-2)\cdot rc[2][w] + ... + 1\cdot rc[N-1][w]) \\ hf[2][w]\times ((N-1)\cdot rc[0][w] + (N-2)\cdot rc[1][w] + (N-3)\cdot rc[2][w] + ... + 1\cdot rc[N-2][w]) \\ hf[3][w]\times ((N-2)\cdot rc[0][w] + (N-3)\cdot rc[1][w] + (N-4)\cdot rc[2][w] + ... + 1\cdot rc[N-3][w]) \\ ... \\ hf[N][w] \times 1 \cdot rc[0][w] \end{matrix}\right.$

如果比较敏感的话应该已经发现突破口了，我们再整理一下：

$dw[w] = \sum_{i=1}^{N}hf[i][w]\sum_{j=0}^{N-i}((N-i-j+1)\cdot rc[j][w])$

还没看出来？再令 $tr[i][w] = \sum_{j=0}^{N-i}((N-i-j+1)\cdot rc[j][w])$ ，这样：

$dw[w] = \sum_{i=1}^{N}hf[i][w]\cdot tr[i][w]$

而且我们还可以发现 $hf, rc, tr$ 它们的递推关系都是差不多的，也就是说对于 $tr$ 我们继续采用考虑相邻两项差的策略：

$tr[i][w] - tr[i-1][w] = \sum_{k=0}^{N-i} rc[k][w]$

这样我们可以用 $O(n^2)$ 的时间把 $tr$ 搞定，这样的话，计算全部的 $dw$ 的值也是 $O(n^2)$ 时间了。

计算好表示定宽度不定高度的图案数的 $dw$ 之后，接下来我们放宽到不定宽度不定高度的图案数，也就是答案，我们有：

$ans = \sum_{w=2}^{M}(M-w+1)\cdot dw[w]$

这样我们绕了一大圈终于把答案算出来了，总复杂度 $O(n^2)$ ，本题至此解决。

实现

NTT+CRT做法

注意这份代码因为常数过大无法通过，但是答案是正确的。

//NTT Version
//Warning:Severely Exceeds TL(14s,TL2s),although O(n^2logn)

#define REP(i,t) for(int i = 0;i < t; i++)
#define REP_1(i,t) for(int i = 1;i <= t; i++)
#define CASE_LOOP int ___;scanf(" %d",&___);for(int __ = 1; __ <= ___; __++)
#define FOR_EDGE(i,u) for (int i = head[u]; i; i = nxt[i])
#define ADHOC_CIN(typ,name) typ name;cin >> name;
#define ADHOC_SCANINT(name) int name;scanf(" %d",&name);


using namespace std;

typedef long long LL;
typedef long double LD;

#define USUAL_MODANY
#ifdef USUAL_MODANY
inline LL getmod(LL a,LL m){if(a<0||a>=m)a%=m;if(a<0)a+=m;return a;}
inline LL summod(LL a,LL b,LL m){return getmod(getmod(a,m)+getmod(b,m),m);}
inline LL mulmod(LL a,LL b,LL m){return getmod(getmod(a,m)*getmod(b,m),m);}
inline LL powmod(LL a,LL p,LL m){LL ret=1;while(p){if(p&1)ret=mulmod(ret,a,m);a=mulmod(a,a,m);p>>=1;}return ret;}
inline LL invmod(LL a,LL m){return powmod(a,m-2,m);}
#endif

#define NTT_MOD_ANY
#ifdef NTT_MOD_ANY
// 多项式乘法 系数对MOD=1000000007取模， 常数巨大，慎用
// 只要选的K个素数乘积大于MOD*MOD*N,理论上MOD可以任取。
#define MOD 1000000007
#define K 3
//用于CRT的三个模空间
const int m[K] = {1004535809, 998244353, 104857601};
//479*2^21+1,7*17*2^23+1,25*2^22+1
//m[0] > m[1] > m[2]
#define G 3
//上述三个素数的原根

const int MAXN = 4444;

inline int qpow(int x, int k, int P) {
    int ret = 1;
    while(k) {
        if(k & 1) ret = 1LL * ret * x % P;
        k >>= 1;
        x = 1LL * x * x % P;
    }
    return ret;
}

struct _NTT {
    //wn:旋转分量 P:模空间(P-1是2的幂)
    int wn[25], P;
    //init(_P)用给出的模空间_P构建旋转分量
    void init(int _P) {
        P = _P;
        for(int i = 1; i <= 21; ++i) {
            int t = 1 << i;
            wn[i] = qpow(G, (P - 1) / t, P);
        }
    }

    //RADAR编码
    //FFT与IFFT之前的反转变换
    //位置i和(i的二进制反转)位置互换
    //len需要是2的幂
    void change(int *y, int len) {
        for(int i = 1, j = len / 2; i < len - 1; ++i) {
            if(i < j) swap(y[i], y[j]);
            int k = len / 2;
            while(j >= k) {
                j -= k;
                k /= 2;
            }
            j += k;
        }
    }

    //NTT主过程，y是等待变换的数组，下标从0开始，长度为len
    //len是2的幂
    //on=1的话NTT on=-1的话INTT
    void NTT(int *y, int len, int on) {
        change(y, len);
        int id = 0;

        for(int h = 2; h <= len; h <<= 1) {
            ++id;
            for(int j = 0; j < len; j += h) {
                int w = 1;
                for(int k = j; k < j + h / 2; ++k) {
                    int u = y[k];
                    int t = 1LL * y[k+h/2] * w % P;
                    y[k] = u + t;
                    if(y[k] >= P) y[k] -= P;
                    y[k+h/2] = u - t + P;
                    if(y[k+h/2] >= P) y[k+h/2] -= P;
                    w = 1LL * w * wn[id] % P;
                }
            }
        }
        if(on == -1) {
            for(int i = 1; i < len / 2; ++i) swap(y[i], y[len-i]);
            int inv = qpow(len, P - 2, P);
            for(int i = 0; i < len; ++i)
                y[i] = 1LL * y[i] * inv % P;
        }
    }

    //自动多项式乘法，结果将会反映到A数组
    //需要事先调整好len至大于离2n最近的2的幂
    void mul(int A[], int B[], int len) {
        NTT(A, len, 1);
        NTT(B, len, 1);
        for(int i = 0; i < len; ++i) A[i] = 1LL * A[i] * B[i] % P;
        NTT(A, len, -1);
    }
}ntt[K];

int tmp[MAXN][K], t1[MAXN], t2[MAXN];
int r[K][K];

//特殊的防爆CRT
//x = x0 + x1*p0 + x2*p0*p1 (% p0*p1*p2) [0<=x0<p0 0<=x1<p1 0<=x2<p2]
//x = a0 (% p0)
//x = a1 (% p1)
//x = a2 (% p2)

//因为我们保证p0*p1*p2>MODER*MODER*n，在P0*p1*p2模空间内，我们计算的原始数值一定只有单个映射
//我们的目的是求出x0 x1 x2,借此用另外一种形式表达x(p0p1p2混合进制形式)
//这样就可以绕开爆LL的问题

//x (%p0) = a0 (%p0) = x0 [因为x0的范围限定在[0,p0),可以看成求出了(% p0*p1*p2)中的x0]
//x (%p1) = a1 (%p1) = x0 + x1*p0 (%p1) [因为p1|p0*p1*p2,在大空间中的x0对应到小空间的位置是确定的]
// --> x1 = (a1 - x0)/p0 (%p1) [因为x1的范围限定在[0,p1),可以看成求出了(% p0*p1*p2)中的x1]
//x (%p2) = a2 (%p2) = x0 + x1*p0 + x2*p0*p1 (%p2) [同上]
// --> x2 = (a2 - x0 - x1*p0)/p0*p1 (%p2) [同上]

int CRT(int a[]) {
    int x[K];
    for(int i = 0; i < K; ++i) {
        x[i] = a[i];
        for(int j = 0; j < i; ++j) {
            int t = (x[i] - x[j]) % m[i];
            if(t < 0) t += m[i];
            x[i] = 1LL * t * r[j][i] % m[i];
        }
    }
    int mul = 1, ret = x[0] % MOD;
    for(int i = 1; i < K; ++i) {
        mul = 1LL * mul * m[i-1] % MOD;
        ret += 1LL * x[i] * mul % MOD;
        if(ret >= MOD) ret -= MOD;
    }
    return ret;
}

//自动多项式乘法，模指定的数(1e9+7)
//len需要调整到离2n最近的2的幂，下标从0开
//结果存入A[]中
//系数模1e9+7就可以
void mul(int A[], int B[], int len) {
    for(int id = 0; id < K; ++id) {
        //转储系数变量
        for(int i = 0; i < len; ++i) {
            t1[i] = A[i];
            t2[i] = B[i];
        }
        //使用id号NTT单元做多项式乘法
        ntt[id].mul(t1, t2, len);
        //转储乘法结果
        for(int i = 0; i < len; ++i)
            tmp[i][id] = t1[i];
    }
    //将乘法结果回射到指定(1e9+7)空间
    for(int i = 0; i < len; ++i) {
        A[i] = CRT(tmp[i]);
    }
}

//预处理逆元r[i][j]:m[i]在m[j]空间内逆元
//初始化需要的NTT单元
void init() {
    for(int i = 0; i < K; ++i) {
        for(int j = 0; j < i; ++j) {
            r[j][i] = qpow(m[j], m[i] - 2, m[i]);
        }
    }
    for(int i = 0; i < K; ++i) {
        ntt[i].init(m[i]);
    }
}

#endif

int N,M;
int hf[MAXN/2][MAXN/2];
void prephf2(){
    for(int w = 2;w < MAXN/2; w++){
        hf[1][w] = 1;
    }
    for(int h = 2;h < MAXN/2;h++){
        int pfx = 0;
        for(int w = 1;w < MAXN/2; w++){
            pfx = summod(pfx, hf[h-1][w],MOD);
            hf[h][w] = summod(hf[h][w-1], pfx,MOD);
        }
    }
}
int al[MAXN/2][MAXN/2];

int f[MAXN/2],g[MAXN/2],pfx[MAXN/2];
int ff[MAXN],gg[MAXN];
void prepal2(){
    for(int h = 1;h <= 2000; h++){
        al[h][2] = 1;
    }

    for (int w = 3; w <= 2000; w++) {
        f[0] = 0;
        g[0] = 1;
        for(int h = 1;h <= 2000; h++){
            f[h] = hf[h][w];
            pfx[h] = summod(pfx[h], hf[h][w-1], MOD);
            g[h] = summod(summod(pfx[h], g[h], MOD), hf[h][w-1], MOD);
        }
        memset(ff, 0, sizeof(ff));
        memset(gg, 0, sizeof(gg));
        for(int j = 0;j <= 2000; j++){
            ff[j] = f[j];
            gg[j] = g[j];
        }
        mul(ff, gg, 4096);
        for(int h = 0;h <= 2000; h++){
            al[h][w] = ff[h];
        }
    }
}

int main(int argc, const char * argv[]){
#ifdef LOCAL_DEBUG
    freopen("testdata.in", "r", stdin);
    clock_t clk = clock();
#endif

    init();
    prephf2();
    prepal2();
    while (cin >> N >> M) {
        LL res = 0;
        for(int h = N;h >= 1; h--){
            LL mpl = N-h+1;
            LL tmp = 0;
            for(int w = M;w >= 2;w--){
                LL mlp = M-w+1;
                tmp = summod(tmp, mulmod(mlp, al[h][w], MOD), MOD);
            }
            res = summod(res, mulmod(mpl, tmp, MOD), MOD);
        }
        cout << res << endl;
    }


#ifdef LOCAL_DEBUG
    puts("-----END OF OUTPUT-----");
    printf("Time Elapsed: %luMS\n",(clock() - clk)/CLK_TCK/10);
#endif

    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251

252

253

254

255

256

257

258

259

260

261

262

263

264

265

266

267

268

269

//NTT Version

//Warning:Severely Exceeds TL(14s,TL2s),although O(n^2logn)

#define REP(i,t) for(int i = 0;i < t; i++)

#define REP_1(i,t) for(int i = 1;i <= t; i++)

#define CASE_LOOP int ___;scanf(" %d",&___);for(int __ = 1; __ <= ___; __++)

#define FOR_EDGE(i,u) for (int i = head[u]; i; i = nxt[i])

#define ADHOC_CIN(typ,name) typ name;cin >> name;

#define ADHOC_SCANINT(name) int name;scanf(" %d",&name);

using namespace std;

typedef long long LL;

typedef long double LD;

#define USUAL_MODANY

#ifdef USUAL_MODANY

inline LL getmod(LL a,LL m){if(a<0||a>=m)a%=m;if(a<0)a+=m;return a;}

inline LL summod(LL a,LL b,LL m){return getmod(getmod(a,m)+getmod(b,m),m);}

inline LL mulmod(LL a,LL b,LL m){return getmod(getmod(a,m)*getmod(b,m),m);}

inline LL powmod(LL a,LL p,LL m){LL ret=1;while(p){if(p&1)ret=mulmod(ret,a,m);a=mulmod(a,a,m);p>>=1;}return ret;}

inline LL invmod(LL a,LL m){return powmod(a,m-2,m);}

#endif

#define NTT_MOD_ANY

#ifdef NTT_MOD_ANY

// 多项式乘法系数对MOD=1000000007取模，常数巨大，慎用

// 只要选的K个素数乘积大于MOD*MOD*N,理论上MOD可以任取。

#define MOD 1000000007

#define K 3

//用于CRT的三个模空间

const int m[K] = {1004535809, 998244353, 104857601};

//479*2^21+1,7*17*2^23+1,25*2^22+1

//m[0] > m[1] > m[2]

#define G 3

//上述三个素数的原根

const int MAXN = 4444;

inline int qpow(int x, int k, int P) {

int ret = 1;

while(k) {

if(k & 1) ret = 1LL * ret * x % P;

k >>= 1;

x = 1LL * x * x % P;

}

return ret;

}

struct _NTT {

//wn:旋转分量 P:模空间(P-1是2的幂)

int wn[25], P;

//init(_P)用给出的模空间_P构建旋转分量

void init(int _P) {

P = _P;

for(int i = 1; i <= 21; ++i) {

int t = 1 << i;

wn[i] = qpow(G, (P - 1) / t, P);

}

//RADAR编码

//FFT与IFFT之前的反转变换

//位置i和(i的二进制反转)位置互换

//len需要是2的幂

void change(int *y, int len) {

for(int i = 1, j = len / 2; i < len - 1; ++i) {

if(i < j) swap(y[i], y[j]);

int k = len / 2;

while(j >= k) {

j -= k;

k /= 2;

}

j += k;

}

//NTT主过程，y是等待变换的数组，下标从0开始，长度为len

//len是2的幂

//on=1的话NTT on=-1的话INTT

void NTT(int *y, int len, int on) {

change(y, len);

int id = 0;

for(int h = 2; h <= len; h <<= 1) {

++id;

for(int j = 0; j < len; j += h) {

int w = 1;

for(int k = j; k < j + h / 2; ++k) {

int u = y[k];

int t = 1LL * y[k+h/2] * w % P;

y[k] = u + t;

if(y[k] >= P) y[k] -= P;

y[k+h/2] = u - t + P;

if(y[k+h/2] >= P) y[k+h/2] -= P;

w = 1LL * w * wn[id] % P;

}

if(on == -1) {

for(int i = 1; i < len / 2; ++i) swap(y[i], y[len-i]);

int inv = qpow(len, P - 2, P);

for(int i = 0; i < len; ++i)

y[i] = 1LL * y[i] * inv % P;

}

//自动多项式乘法，结果将会反映到A数组

//需要事先调整好len至大于离2n最近的2的幂

void mul(int A[], int B[], int len) {

NTT(A, len, 1);

NTT(B, len, 1);

for(int i = 0; i < len; ++i) A[i] = 1LL * A[i] * B[i] % P;

NTT(A, len, -1);

}

}ntt[K];

int tmp[MAXN][K], t1[MAXN], t2[MAXN];

int r[K][K];

//特殊的防爆CRT

//x = x0 + x1*p0 + x2*p0*p1 (% p0*p1*p2) [0<=x0<p0 0<=x1<p1 0<=x2<p2]

//x = a0 (% p0)

//x = a1 (% p1)

//x = a2 (% p2)

//因为我们保证p0*p1*p2>MODER*MODER*n，在P0*p1*p2模空间内，我们计算的原始数值一定只有单个映射

//我们的目的是求出x0 x1 x2,借此用另外一种形式表达x(p0p1p2混合进制形式)

//这样就可以绕开爆LL的问题

//x (%p0) = a0 (%p0) = x0 [因为x0的范围限定在[0,p0),可以看成求出了(% p0*p1*p2)中的x0]

//x (%p1) = a1 (%p1) = x0 + x1*p0 (%p1) [因为p1|p0*p1*p2,在大空间中的x0对应到小空间的位置是确定的]

// --> x1 = (a1 - x0)/p0 (%p1) [因为x1的范围限定在[0,p1),可以看成求出了(% p0*p1*p2)中的x1]

//x (%p2) = a2 (%p2) = x0 + x1*p0 + x2*p0*p1 (%p2) [同上]

// --> x2 = (a2 - x0 - x1*p0)/p0*p1 (%p2) [同上]

int CRT(int a[]) {

int x[K];

for(int i = 0; i < K; ++i) {

x[i] = a[i];

for(int j = 0; j < i; ++j) {

int t = (x[i] - x[j]) % m[i];

if(t < 0) t += m[i];

x[i] = 1LL * t * r[j][i] % m[i];

}

int mul = 1, ret = x[0] % MOD;

for(int i = 1; i < K; ++i) {

mul = 1LL * mul * m[i-1] % MOD;

ret += 1LL * x[i] * mul % MOD;

if(ret >= MOD) ret -= MOD;

}

return ret;

}

//自动多项式乘法，模指定的数(1e9+7)

//len需要调整到离2n最近的2的幂，下标从0开

//结果存入A[]中

//系数模1e9+7就可以

void mul(int A[], int B[], int len) {

for(int id = 0; id < K; ++id) {

//转储系数变量

for(int i = 0; i < len; ++i) {

t1[i] = A[i];

t2[i] = B[i];

}

//使用id号NTT单元做多项式乘法

ntt[id].mul(t1, t2, len);

//转储乘法结果

for(int i = 0; i < len; ++i)

tmp[i][id] = t1[i];

}

//将乘法结果回射到指定(1e9+7)空间

for(int i = 0; i < len; ++i) {

A[i] = CRT(tmp[i]);

}

//预处理逆元r[i][j]:m[i]在m[j]空间内逆元

//初始化需要的NTT单元

void init() {

for(int i = 0; i < K; ++i) {

for(int j = 0; j < i; ++j) {

r[j][i] = qpow(m[j], m[i] - 2, m[i]);

}

for(int i = 0; i < K; ++i) {

ntt[i].init(m[i]);

}

#endif

int N,M;

int hf[MAXN/2][MAXN/2];

void prephf2(){

for(int w = 2;w < MAXN/2; w++){

hf[1][w] = 1;

}

for(int h = 2;h < MAXN/2;h++){

int pfx = 0;

for(int w = 1;w < MAXN/2; w++){

pfx = summod(pfx, hf[h-1][w],MOD);

hf[h][w] = summod(hf[h][w-1], pfx,MOD);

}

int al[MAXN/2][MAXN/2];

int f[MAXN/2],g[MAXN/2],pfx[MAXN/2];

int ff[MAXN],gg[MAXN];

void prepal2(){

for(int h = 1;h <= 2000; h++){

al[h][2] = 1;

}

for (int w = 3; w <= 2000; w++) {

f[0] = 0;

g[0] = 1;

for(int h = 1;h <= 2000; h++){

f[h] = hf[h][w];

pfx[h] = summod(pfx[h], hf[h][w-1], MOD);

g[h] = summod(summod(pfx[h], g[h], MOD), hf[h][w-1], MOD);

}

memset(ff, 0, sizeof(ff));

memset(gg, 0, sizeof(gg));

for(int j = 0;j <= 2000; j++){

ff[j] = f[j];

gg[j] = g[j];

}

mul(ff, gg, 4096);

for(int h = 0;h <= 2000; h++){

al[h][w] = ff[h];

}

int main(int argc, const char * argv[]){

#ifdef LOCAL_DEBUG

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

clock_t clk = clock();

#endif

init();

prephf2();

prepal2();

while (cin >> N >> M) {

LL res = 0;

for(int h = N;h >= 1; h--){

LL mpl = N-h+1;

LL tmp = 0;

for(int w = M;w >= 2;w--){

LL mlp = M-w+1;

tmp = summod(tmp, mulmod(mlp, al[h][w], MOD), MOD);

}

res = summod(res, mulmod(mpl, tmp, MOD), MOD);

}

cout << res << endl;

}

#ifdef LOCAL_DEBUG

puts("-----END OF OUTPUT-----");

printf("Time Elapsed: %luMS\n",(clock() - clk)/CLK_TCK/10);

#endif

return 0;

}

正解

//Accepted Version
//Enumerate w
//Enumerate upper part (xxxx5)
//preCalculate lower part (4xxx) product times
//This can make in O(n^2) time
//No NTT required
#define REP(i,t) for(int i = 0;i < t; i++)
#define REP_1(i,t) for(int i = 1;i <= t; i++)
#define CASE_LOOP int ___;scanf(" %d",&___);for(int __ = 1; __ <= ___; __++)
#define FOR_EDGE(i,u) for (int i = head[u]; i; i = nxt[i])
#define ADHOC_CIN(typ,name) typ name;cin >> name;
#define ADHOC_SCANINT(name) int name;scanf(" %d",&name);

using namespace std;

typedef long long LL;
typedef long double LD;

#define USUAL_MOD1E9
#ifdef USUAL_MOD1E9
const LL MODER = 1000000007;
LL getmod(LL a){if(a<0||a>=MODER)a%=MODER;if(a<0)a+=MODER;return a;}
LL summod(LL a,LL b){return getmod(getmod(a)+getmod(b));}
LL mulmod(LL a,LL b){return getmod(getmod(a)*getmod(b));}
LL powmod(LL a,LL p){LL ret=1;while(p){if(p&1)ret=mulmod(ret,a);a=mulmod(a,a);p>>=1;}return ret;}
LL invmod(LL a){return powmod(a,MODER-2);}
#endif

const int MAXN = 2005;
int N,M;
int hf[MAXN][MAXN];
void prephf(){
    for(int w = 2;w < MAXN; w++){
        hf[1][w] = 1;
    }
    for(int h = 2;h < MAXN;h++){
        int pfx = 0;
        for(int w = 1;w < MAXN; w++){
            pfx = summod(pfx, hf[h-1][w]);
            hf[h][w] = summod(hf[h][w-1], pfx);
        }
    }
}
int lower[MAXN][MAXN];
void preplower(){
    REP_1(h, MAXN-1){
        int pfx = 0;
        for(int w = 2;w < MAXN; w++){
            pfx = summod(pfx, hf[h][w]);
            lower[h][w] = summod(lower[h][w-1], summod(pfx, hf[h][w]));
        }
    }
}
int sml[MAXN][MAXN];
void prepsml(){
    REP_1(w, MAXN-1){
        int pfx = 0;
        REP_1(h, MAXN-1){
            pfx = summod(pfx,lower[h][w]);
            sml[h][w] = summod(sml[h-1][w], pfx);
        }
    }
}

void prep(){
    prephf();
    preplower();
    prepsml();
}

void solve(){
    int res = 0;
    REP_1(w, M){
        int tim = M+1-w;
        int tmp = 0;
        REP_1(upper, N){
            tmp = summod(tmp, mulmod(hf[upper][w], (N+1-upper)));
            tmp = summod(tmp, mulmod(hf[upper][w], sml[N-upper][w-1]));
        }
        res = summod(res, mulmod(tmp, tim));
    }
    cout << res << endl;
}

int main(int argc, const char * argv[]){
#ifdef LOCAL_DEBUG
    freopen("testdata.in", "r", stdin);
    clock_t clk = clock();
#endif

    prep();
    while (cin >> N >> M) {
        solve();
    }

#ifdef LOCAL_DEBUG
    puts("-----END OF OUTPUT-----");
    printf("Time Elapsed: %luMS\n",(clock() - clk)/CLK_TCK/10);
#endif

    return 0;
}

100

101

102

//Accepted Version

//Enumerate w

//Enumerate upper part (xxxx5)

//preCalculate lower part (4xxx) product times

//This can make in O(n^2) time

//No NTT required

#define REP(i,t) for(int i = 0;i < t; i++)

#define REP_1(i,t) for(int i = 1;i <= t; i++)

#define CASE_LOOP int ___;scanf(" %d",&___);for(int __ = 1; __ <= ___; __++)

#define FOR_EDGE(i,u) for (int i = head[u]; i; i = nxt[i])

#define ADHOC_CIN(typ,name) typ name;cin >> name;

#define ADHOC_SCANINT(name) int name;scanf(" %d",&name);

using namespace std;

typedef long long LL;

typedef long double LD;

#define USUAL_MOD1E9

#ifdef USUAL_MOD1E9

const LL MODER = 1000000007;

LL getmod(LL a){if(a<0||a>=MODER)a%=MODER;if(a<0)a+=MODER;return a;}

LL summod(LL a,LL b){return getmod(getmod(a)+getmod(b));}

LL mulmod(LL a,LL b){return getmod(getmod(a)*getmod(b));}

LL powmod(LL a,LL p){LL ret=1;while(p){if(p&1)ret=mulmod(ret,a);a=mulmod(a,a);p>>=1;}return ret;}

LL invmod(LL a){return powmod(a,MODER-2);}

#endif

const int MAXN = 2005;

int N,M;

int hf[MAXN][MAXN];

void prephf(){

for(int w = 2;w < MAXN; w++){

hf[1][w] = 1;

}

for(int h = 2;h < MAXN;h++){

int pfx = 0;

for(int w = 1;w < MAXN; w++){

pfx = summod(pfx, hf[h-1][w]);

hf[h][w] = summod(hf[h][w-1], pfx);

}

int lower[MAXN][MAXN];

void preplower(){

REP_1(h, MAXN-1){

int pfx = 0;

for(int w = 2;w < MAXN; w++){

pfx = summod(pfx, hf[h][w]);

lower[h][w] = summod(lower[h][w-1], summod(pfx, hf[h][w]));

}

int sml[MAXN][MAXN];

void prepsml(){

REP_1(w, MAXN-1){

int pfx = 0;

REP_1(h, MAXN-1){

pfx = summod(pfx,lower[h][w]);

sml[h][w] = summod(sml[h-1][w], pfx);

}

void prep(){

prephf();

preplower();

prepsml();

}

void solve(){

int res = 0;

REP_1(w, M){

int tim = M+1-w;

int tmp = 0;

REP_1(upper, N){

tmp = summod(tmp, mulmod(hf[upper][w], (N+1-upper)));

tmp = summod(tmp, mulmod(hf[upper][w], sml[N-upper][w-1]));

}

res = summod(res, mulmod(tmp, tim));

}

cout << res << endl;

}

int main(int argc, const char * argv[]){

#ifdef LOCAL_DEBUG

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

clock_t clk = clock();

#endif

prep();

while (cin >> N >> M) {

solve();

}

#ifdef LOCAL_DEBUG

puts("-----END OF OUTPUT-----");

printf("Time Elapsed: %luMS\n",(clock() - clk)/CLK_TCK/10);

#endif

return 0;

}

参考

kmjpさん（日本語注意）：
http://kmjp.hatenablog.jp/entry/2014/09/22/0900

Zeyu_king：
http://blog.csdn.net/zeyu_king/article/details/44040749

给中级者的动态规划教程

January 21, 20162016-01-21hahaschoolLeave a comment

认识更多模型

区间DP

POJ 2955 Brackets：最简单的区间DP，括号序列

LA4394 String Painter：两层区间DP，难度较大

概率DP

POJ 3744 Scout YYF I：概率型递推配合矩阵快速幂加速

POJ 2096 Collecting Bugs：优惠券问题的二维情形

状态压缩DP

UVA 10911 Forming Quiz Teams：最优配对问题

LA3725 Hie with the Pie：TSP问题

树DP

POJ 1655 Balancing Act：求树的重心

Codeforces 461B Appleman and Tree：最大独立集问题的变种

LA4394 String Painter

January 21, 20162016-01-21hahaschoolLeave a comment

题意

给定两个长度相等，只有小写字母构成的字符串s和t，每步可以把s的一个连续子串“刷”成同一个字母，问至少多少步才能把s变成t。

思路

两层区间DP。

首先忽略原始串s，只去看目标串t，设dp1[i][j]表示从什么都没有的情况下利用刷子规则构造出目标串t的i到j这一段所需要的最小操作次数。这里着眼于“最后一次操作”进行阶段的划分。

dp1的状态转移：

dp[i][j] = dp[i+1][j ] + 1
先默认最后一次操作是只刷出最新那个字符。
令k是i和j中间的某个位置，t是目标串，如果t[i] == t[k]
尝试用dp[i+1][k] + dp[k+1][j]更新dp[i][j]
因为i处字符等于k处字符，在构造i+1到k这个区段的时候，可以在刷k处字符的同时“顺便”把i位置也给刷了。
注意这里不可以写成dp[i+1][k-1] + 1 + dp[k+1][j]，考虑反例” /e(i对应)/ee/e(k对应)/… “,在这里dp[i+1][k-1]是1，用这种错误的算法dp[i][k]部分会变成2，但实际上应该是1。

接下来引入原始串s，令dp2[i]表示把原始串1到i构造成目标串1到i的部分所需要的最小的操作次数。这里有状态转移：

默认dp2 = dp1[1][i]
如果s[i] == t[i]
尝试dp2[i] = dp2[i-1]
否则尝试dp2[i] = dp2[i-1] + 1

这里的意思是如果在第i位两个串对应字符相等，可以选择无需对这一位进行操作
令k是1到i之间的位置
尝试dp2[i] = dp2[k-1] + dp1[k][j]

这里的意思是假设最后k位使用不考虑原始状态的构造方法，前面继承最优解。为什么要这样做？考虑fabcf这样的区间，一种较好的策略是先都刷成f，然后分别刷好abc，如果你选择这么做了，相当于已经无视了原来串的样子，因为第一步已经将全部中间字符都刷成f了。

代码

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <set>
#include <stack>
#include <cmath>

using namespace std;

int dp[105][105];
int res[105];

int main(){
    string a,b;
    while(cin >> a >> b){
        memset(dp,0,sizeof(dp));
        memset(res,0,sizeof(res));
        int n = (int)a.size();
        for(int i = 1;i <= n;i++){
            dp[i][i] = 1;
        }
        for(int i = n-1;i >= 1;i--){
            for(int j = i+1;j <= n;j++){
                dp[i][j] = dp[i+1][j] + 1;
                for(int k = i+1;k <= j;k++){
                    if(b[i-1] == b[k-1]){
                        dp[i][j] = min(dp[i][j],dp[i+1][k]+dp[k+1][j]);
                    }

                }
            }
        }
        for(int i = 1;i <= n ;i++){
            res[i] = min(dp[1][i],res[i-1]+(a[i-1] != b[i-1]));
            for(int j = 1;j <= i;j++){
                res[i] = min(res[i],res[j]+dp[j+1][i]);
            }
        }
        cout << res[n] << endl;
    }
    return 0;
}

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

#include <stack>

#include <cmath>

using namespace std;

int dp[105][105];

int res[105];

int main(){

string a,b;

while(cin >> a >> b){

memset(dp,0,sizeof(dp));

memset(res,0,sizeof(res));

int n = (int)a.size();

for(int i = 1;i <= n;i++){

dp[i][i] = 1;

}

for(int i = n-1;i >= 1;i--){

for(int j = i+1;j <= n;j++){

dp[i][j] = dp[i+1][j] + 1;

for(int k = i+1;k <= j;k++){

if(b[i-1] == b[k-1]){

dp[i][j] = min(dp[i][j],dp[i+1][k]+dp[k+1][j]);

}

for(int i = 1;i <= n ;i++){

res[i] = min(dp[1][i],res[i-1]+(a[i-1] != b[i-1]));

for(int j = 1;j <= i;j++){

res[i] = min(res[i],res[j]+dp[j+1][i]);

}

cout << res[n] << endl;

}

return 0;

}

LA3725 Hie with the Pie

January 21, 20162016-01-21hahaschoolLeave a comment

题意

经典问题：TSP。

给出了n个城市，求一条最短的路径，使得经过每个城市一次且仅一次，最后回到起点。

思路

状态压缩DP。分析问题可知道是一个多阶段决策过程，每个阶段“状态”包括了可以用已经走了哪些点，和当前站在哪个点，决策就是接下来走哪个点。

状态表示：dp[二进制位，表示目前已经走过那些点][最后走的点的序号] = 从起点出发走过的最短路程

答案：min{dp[走过全部点的状态][枚举各个可能的最后走的点i] + dis(i,起点)}

边界：dp[0][起点] = 0,其它都是INF

状态转移：用dp[S][i] + dis(i,j) 去尝试更新dp[S|j][j]

代码

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <set>
#include <stack>
#include <cmath>
#include <map>

using namespace std;

int n;
long long dis[12][12];
long long dp[12][4096];

void floyd_warshall(){
    for (int k = 0; k <=n;k++) {
        for(int i = 0; i<= n; i++){
            for(int j = 0; j<=n ;j++){
                if(dis[i][k] + dis[k][j] < dis[i][j]){
                    dis[i][j] = dis[i][k] + dis[k][j];
                }
            }
        }
    }
}

long long solve(){
    memset(dp, 0x3f, sizeof(dp));
    for(int i = 0; i < (1 << n) ;i++){
        int cnt = 0,lst = 0;
        for(int j = 1; j <= n; j++){
            if(i & (1 << (j-1))){
                cnt++;
                lst = j;
            }
        }
        if(cnt <= 1){
            dp[lst][i] = dis[0][lst];
        }else{
            for(int j = 1; j <= n; j++){
                if(i & (1 << (j-1))){
                    for(int k = 1; k <= n; k++){
                        if(j != k && i & (1 << (k-1))){
                            dp[j][i] = min(dp[j][i],dp[k][i^(1 << (j-1))] + dis[k][j]);
                        }
                    }
                }
            }
        }
    }
    long long ret = 0x3f3f3f3f3f3f3f3f;
    for(int i = 1; i<=n;i++){
        ret = min(ret,dp[i][(1 << n)-1] + dis[i][0]);
    }
    return ret;
}

int main(){
    //freopen("testdata.in", "r", stdin);
    while(scanf(" %d",&n) != EOF && n){
        for(int i = 0; i <= n ;i++){
            for(int j =0;j <= n; j++){
                scanf(" %lld",&dis[i][j]);
            }
        }
        floyd_warshall();
        printf("%lld\n",solve());
    }

    return 0;
}

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

#include <stack>

#include <cmath>

#include <map>

using namespace std;

int n;

long long dis[12][12];

long long dp[12][4096];

void floyd_warshall(){

for (int k = 0; k <=n;k++) {

for(int i = 0; i<= n; i++){

for(int j = 0; j<=n ;j++){

if(dis[i][k] + dis[k][j] < dis[i][j]){

dis[i][j] = dis[i][k] + dis[k][j];

}

long long solve(){

memset(dp, 0x3f, sizeof(dp));

for(int i = 0; i < (1 << n) ;i++){

int cnt = 0,lst = 0;

for(int j = 1; j <= n; j++){

if(i & (1 << (j-1))){

cnt++;

lst = j;

}

if(cnt <= 1){

dp[lst][i] = dis[0][lst];

}else{

for(int j = 1; j <= n; j++){

if(i & (1 << (j-1))){

for(int k = 1; k <= n; k++){

if(j != k && i & (1 << (k-1))){

dp[j][i] = min(dp[j][i],dp[k][i^(1 << (j-1))] + dis[k][j]);

}

long long ret = 0x3f3f3f3f3f3f3f3f;

for(int i = 1; i<=n;i++){

ret = min(ret,dp[i][(1 << n)-1] + dis[i][0]);

}

return ret;

}

int main(){

//freopen("testdata.in", "r", stdin);

while(scanf(" %d",&n) != EOF && n){

for(int i = 0; i <= n ;i++){

for(int j =0;j <= n; j++){

scanf(" %lld",&dis[i][j]);

}

floyd_warshall();

printf("%lld\n",solve());

}

return 0;

}

UVA 10911 Forming Quiz Teams

January 21, 20162016-01-21hahaschoolLeave a comment

题意

经典模型“最优配对问题”，给出了平面上若干个点，你要把牠们两两配对，使得每一对中两点距离之和最小。

思路

分析问题：我们发现，本问题可以着眼于“最后一次配对”，是一个多阶段决策。不妨考虑当最后一次选择拿i号点去和j号点去配对,得到了某种状态时可以得到的最优解。

状态表示：dp[当前状态下各个点是否已经配对][最后一次配对的点i][最后一次配对的点j]

我们发现这个状态设的太繁了，假如我们要配对a和b这两个点，那么在所有的配对状态里面都要算入a和b的距离，在所有没配对状态里都不可以算入a和b的距离，后两个维度强行决定了一组点的配对情况，然而并没有什么意义，因为后两个维度的信息已经包括进了第一个维度里，我们只要想办法让第一个维度可以表达出决策的“分阶段”特性，能够识别出最后一步是什么就可以。

于是我们重设状态：dp[当前状态下各个点是否已经配对]并且规定在每个状态中，最低位为1对应的那个点是我们最后一次操作的点。

这样有状态转移：dp[S] = min{dis(i,j) + dp[S^i^j]} 在这里S是二进制表示的状态，i,j是假定的最后一次配对的点对，其中规定i一定是S中最低位的那个点，dis表示求距离，S^i^j表示将二进制表示的状态中i,j对应的位设成零之后得到的二进制状态

代码

#include <iostream>
#include <cstdio>

using namespace std;

int n;
struct Student{
    double x;
    double y;
    string name;
} stu[17];

double dis(Student &a,Student &b){
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}

double dp[17][100000];

double solve(){
    memset(dp, 0x77, sizeof(dp));
    dp[0][0] = 0;
    dp[1][0] = 0;
    dp[1][1] = 0;
    for(int i = 2;i <= n; i++){
        for(int j = 0; j < (1 << i) ;j++){
            if(j&(1 << (i-1))){
                for(int k = 1; k < i; k++){
                    if(j & (1 << (k-1))){
                        dp[i][j] = min(dp[i][j],dp[i-1][j^(1 << (i-1))^(1 << (k-1))] + dis(stu[i], stu[k]));
                    }
                }
            }else{
                dp[i][j] = dp[i-1][j];
            }

        }
    }
    return dp[n][(1 << n)-1];
}

int main(){
    int caseCnt = 0;
    while(cin >> n){
        if(!n){
            break;
        }
        n *= 2;
        caseCnt++;
        for(int i = 1; i <= n; i++){
            cin >> stu[i].name >> stu[i].x >> stu[i].y;
        }
        cout << "Case " << caseCnt << ": "  << fixed << setprecision(2) << solve() << endl;
    }

    return 0;
}

#include <iostream>

#include <cstdio>

using namespace std;

int n;

struct Student{

double x;

double y;

string name;

} stu[17];

double dis(Student &a,Student &b){

return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));

}

double dp[17][100000];

double solve(){

memset(dp, 0x77, sizeof(dp));

dp[0][0] = 0;

dp[1][0] = 0;

dp[1][1] = 0;

for(int i = 2;i <= n; i++){

for(int j = 0; j < (1 << i) ;j++){

if(j&(1 << (i-1))){

for(int k = 1; k < i; k++){

if(j & (1 << (k-1))){

dp[i][j] = min(dp[i][j],dp[i-1][j^(1 << (i-1))^(1 << (k-1))] + dis(stu[i], stu[k]));

}

}else{

dp[i][j] = dp[i-1][j];

}

return dp[n][(1 << n)-1];

}

int main(){

int caseCnt = 0;

while(cin >> n){

if(!n){

break;

}

n *= 2;

caseCnt++;

for(int i = 1; i <= n; i++){

cin >> stu[i].name >> stu[i].x >> stu[i].y;

}

cout << "Case " << caseCnt << ": " << fixed << setprecision(2) << solve() << endl;

}

return 0;

}

POJ 2955 Brackets

January 21, 20162016-01-21hahaschoolOne Comment

题意

给出一个由小括号喝中括号组成的括号序列，定义正规括号序列为(),[],(s),[s],其中s也是正规括号序列。求最长正规括号序列的长度。

思路

考虑区间DP，设计状态时着眼于“最后一次加括号”。

状态表示：dp[i][j] = 从 i 到 j 的（包含i,j）最长的括号序列长度。

状态转移：

dp[i][j] = dp[i][j-1] 继承上一个区间的结果
令k为i,j之间的一个位置，str是给出的括号串(令下标从1开始)
如果str[k]与str[j]正好是一对匹配的括号，可以考虑在最后一步放这个括号，用dp[i][k] + 2 + dp[k+1][j-1]尝试更新dp[i][j]

答案：dp[1][len]

初始化：直接令整个dp数组都为0，既可以完成初始化，也可以无效化所有无效状态。

代码

#include <stdio.h>
#include <iostream>

using namespace std;
const int MAXN = 105;
char str[MAXN];
int len;
int dp[MAXN][MAXN];//dp[from][to] = maximum rectified seq len btw from and to

void solve(){
    memset(dp, 0, sizeof(dp));
    for(int i = len; i >= 1; i--){
        dp[i][i] = 0;
        for(int j = i+1; j <= len; j++){
            dp[i][j] = dp[i][j-1];
            for(int k = i; k <= j; k++){
                if ((str[k-1] == '(' && str[j-1] == ')') ||
                    (str[k-1] == '[' && str[j-1] == ']')) {
                    dp[i][j] = max(dp[i][j],dp[i][k-1] + 2 + dp[k+1][j-1]);
                }
            }
        }
    }
    printf("%d\n",dp[1][len]);
}

int main(){
    while(scanf(" %s",str) != EOF){
        if(str[0] == 'e'){
            break;
        }
        len = (int)strlen(str);
        solve();
    }
    return 0;
}

#include <stdio.h>

#include <iostream>

using namespace std;

const int MAXN = 105;

char str[MAXN];

int len;

int dp[MAXN][MAXN];//dp[from][to] = maximum rectified seq len btw from and to

void solve(){

memset(dp, 0, sizeof(dp));

for(int i = len; i >= 1; i--){

dp[i][i] = 0;

for(int j = i+1; j <= len; j++){

dp[i][j] = dp[i][j-1];

for(int k = i; k <= j; k++){

if ((str[k-1] == '(' && str[j-1] == ')') ||

(str[k-1] == '[' && str[j-1] == ']')) {

dp[i][j] = max(dp[i][j],dp[i][k-1] + 2 + dp[k+1][j-1]);

}

printf("%d\n",dp[1][len]);

}

int main(){

while(scanf(" %s",str) != EOF){

if(str[0] == 'e'){

break;

}

len = (int)strlen(str);

solve();

}

return 0;

}

POJ 2114 Boatherds

December 06, 20152015-12-06hahaschoolLeave a comment

题意

给出一棵树，树边带有边权，问你能不能找出一条路径使得路径边权之和正好等于给出的k值。

思路

和这个题非常像，只不过题意从计算有多少点对之间距离小于k换成了判断有没有一条路径等于k。但实际上可以用一套思路解决。

代码

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <set>
#include <stack>
#include <cmath>
#include <map>
#include <complex>

using namespace std;

const int MAXV = 100005;
const int MAXE = 200005;
const int INF = 0x3f3f3f3f;

int nxt[MAXE],end[MAXE],head[MAXV],cost[MAXE],gtot,vis[MAXV];
int n;

void init(){
    gtot = 2;
    for(int i = 1; i<=n; i++){
        head[i] = 0;
    }
}
void addEdge(int from,int to,int _cost){
    end[gtot] = to;
    cost[gtot] = _cost;
    nxt[gtot] = head[from];
    head[from] = gtot++;
}

int siz[MAXV],midpn,bal;
void getbal(int cur,int par,int totsiz){
    siz[cur] = 1;
    int dpn = 1;
    for(int j = head[cur]; j; j = nxt[j]){
        int now = end[j];
        if(now != par && !vis[now]){
            getbal(now,cur,totsiz);
            siz[cur] += siz[now];
            dpn = max(dpn,siz[now]);
        }
    }
    dpn = max(dpn,totsiz-siz[cur]);
    if(dpn < midpn){
        midpn = dpn;
        bal = cur;
    }
}

int dis[MAXV],distot;
void dfs_dis(int cur,int par,int hav = 0){
    dis[distot++] = hav;
    siz[cur] = 1;
    for(int j = head[cur]; j; j = nxt[j]){
        int now = end[j];
        if(now != par && !vis[now]){
            dfs_dis(now,cur,hav+cost[j]);
            siz[cur] += siz[now];
        }
    }
}

int calc(int rt,int k){
    int ret = 0;
    distot = 0;
    dfs_dis(rt,0);
    sort(dis,dis+distot);
    for(int i = 0; i < distot; i++){
        pair<int*,int*> bin = equal_range(dis+i+1,dis+distot,k-dis[i]);
        ret += bin.second - bin.first;
    }
    return ret;
}

bool dfs_main(int cur,int k){
    int cnt = 0;
    cnt += calc(cur,k);
    vis[cur] = true;
    for(int j = head[cur]; j; j = nxt[j]){
        int now = end[j];
        if(!vis[now]){
            cnt -= calc(now,k-2*cost[j]);
        }
    }
    if(cnt > 0){
        return true;
    }else{
        for(int j = head[cur]; j; j = nxt[j]){
            int now = end[j];
            if(!vis[now]){
                midpn = INF;
                getbal(now,cur,siz[now]);
                if(dfs_main(bal,k)){
                    return true;
                }
            }
        }
    }
    return false;
}

bool solve(int k){
    for(int i = 1; i<= n; i++){
        vis[i] = false;
    }
    midpn = INF;
    getbal(1,0,n);
    return dfs_main(bal,k);
}


int main(){
    while(scanf(" %d",&n) != EOF && n){
        init();
        for(int i = 1; i <= n; i++){
            int a,b;
            while(scanf(" %d",&a) != EOF && a){
                scanf(" %d",&b);
                addEdge(i,a,b);
                addEdge(a,i,b);
            }
        }
        int q;
        while(scanf(" %d",&q) != EOF && q){
            if(solve(q)){
                puts("AYE");
            }else{
                puts("NAY");
            }
        }
        puts(".");
    }

}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

#include <stack>

#include <cmath>

#include <map>

#include <complex>

using namespace std;

const int MAXV = 100005;

const int MAXE = 200005;

const int INF = 0x3f3f3f3f;

int nxt[MAXE],end[MAXE],head[MAXV],cost[MAXE],gtot,vis[MAXV];

int n;

void init(){

gtot = 2;

for(int i = 1; i<=n; i++){

head[i] = 0;

}

void addEdge(int from,int to,int _cost){

end[gtot] = to;

cost[gtot] = _cost;

nxt[gtot] = head[from];

head[from] = gtot++;

}

int siz[MAXV],midpn,bal;

void getbal(int cur,int par,int totsiz){

siz[cur] = 1;

int dpn = 1;

for(int j = head[cur]; j; j = nxt[j]){

int now = end[j];

if(now != par && !vis[now]){

getbal(now,cur,totsiz);

siz[cur] += siz[now];

dpn = max(dpn,siz[now]);

}

dpn = max(dpn,totsiz-siz[cur]);

if(dpn < midpn){

midpn = dpn;

bal = cur;

}

int dis[MAXV],distot;

void dfs_dis(int cur,int par,int hav = 0){

dis[distot++] = hav;

siz[cur] = 1;

for(int j = head[cur]; j; j = nxt[j]){

int now = end[j];

if(now != par && !vis[now]){

dfs_dis(now,cur,hav+cost[j]);

siz[cur] += siz[now];

}

int calc(int rt,int k){

int ret = 0;

distot = 0;

dfs_dis(rt,0);

sort(dis,dis+distot);

for(int i = 0; i < distot; i++){

pair<int*,int*> bin = equal_range(dis+i+1,dis+distot,k-dis[i]);

ret += bin.second - bin.first;

}

return ret;

}

bool dfs_main(int cur,int k){

int cnt = 0;

cnt += calc(cur,k);

vis[cur] = true;

for(int j = head[cur]; j; j = nxt[j]){

int now = end[j];

if(!vis[now]){

cnt -= calc(now,k-2*cost[j]);

}

if(cnt > 0){

return true;

}else{

for(int j = head[cur]; j; j = nxt[j]){

int now = end[j];

if(!vis[now]){

midpn = INF;

getbal(now,cur,siz[now]);

if(dfs_main(bal,k)){

return true;

}

return false;

}

bool solve(int k){

for(int i = 1; i<= n; i++){

vis[i] = false;

}

midpn = INF;

getbal(1,0,n);

return dfs_main(bal,k);

}

int main(){

while(scanf(" %d",&n) != EOF && n){

init();

for(int i = 1; i <= n; i++){

int a,b;

while(scanf(" %d",&a) != EOF && a){

scanf(" %d",&b);

addEdge(i,a,b);

addEdge(a,i,b);

}

int q;

while(scanf(" %d",&q) != EOF && q){

if(solve(q)){

puts("AYE");

}else{

puts("NAY");

}

puts(".");

}

POJ 1987 Distance Statistics

December 06, 20152015-12-06hahaschoolOne Comment

题意

给出一棵树，和树上两点之间的边权大小，要你快速回答出树上有多少不同的点对使的这对点之间的距离至多为k。

思路

典型的点分治问题。

当考虑一棵有根树中有多少点对的距离小于等于k时，可以求出所有节点到根部的距离，然后使用二分，或者尺取的方法得到有多少对点之间的距离小于等于k。但是在上面的计算过程中我们想要求的是经过根部的符合要求的点对数量，但实际上多算入了一些并不符合要求的点，同时也漏掉了不经过根部的符合条件的点对。

所以我们可以这样看：一棵树的符合条件点对数=上面所述方法找出的点对数-各个子树中两点间距小于等于(k-2e)的点对数目(e是根部到孩子的树边的边权)+各个子树符合条件的点对数

上面的式子是递归的，这是一个树分治（点分治）策略。

在实现树分治的时候，一定要注意只有配合了重心的点分治才能达到O(nlogn)的复杂度，否则会面临特殊情况（比如链）退化到O(n^2).

代码

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <set>
#include <stack>
#include <cmath>
#include <map>
#include <complex>

using namespace std;

const int MAXV = 40005;
const int MAXE = 80005;

int N,M,K;

int head[MAXV],nxt[MAXE],to[MAXE],len[MAXE],vis[MAXV],gphtot;
void gph_init(){
    gphtot = 2;
    memset(head,0,sizeof(head));
    memset(vis,0,sizeof(vis));
}
void gph_addEdge(int from,int _to,int cost){
    to[gphtot] = _to;
    nxt[gphtot] = head[from];
    len[gphtot] = cost;
    head[from] = gphtot++;
}
void input(){
    scanf(" %d %d",&N,&M);
    gph_init();
    for(int i = 1; i <= M; i++){
        int a,b,c;
        char d;
        scanf(" %d %d %d %c",&a,&b,&c,&d);
        gph_addEdge(a,b,c);
        gph_addEdge(b,a,c);
    }
    scanf(" %d",&K);
}

int siz[MAXV],mic,bal;
void getbal(int cur,int par,int totsiz){
    int mxc = 0;
    siz[cur] = 1;
    for(int j = head[cur]; j; j = nxt[j]){
        int now = to[j];
        if(now != par && !vis[now]){
            getbal(now,cur,totsiz);
            siz[cur] += siz[now];
            mxc = max(mxc,siz[now]);
        }
    }
    mxc = max(mxc,totsiz - siz[cur]);
    if(mic > mxc){
        mic = mxc;
        bal = cur;
    }
}

int dis[MAXV],distot;
void dfs_dis(int cur,int par,int hav = 0){
    dis[distot++] = hav;
    siz[cur] = 1;
    for(int j = head[cur]; j; j = nxt[j]){
        int now = to[j];
        if(now != par && !vis[now]){
            dfs_dis(now,cur,hav+len[j]);
            siz[cur] += siz[now];
        }
    }
}
int calc(int rt,int k){
    distot = 0;
    dfs_dis(rt,0,k);
    int ret = 0;
    sort(dis,dis+distot);
    int r = distot - 1;
    for(int l = 0; l < distot; l++){
        while(dis[r] + dis[l] > K){
            r--;
        }
        if(r <= l){
            break;
        }
        ret += r-l;
    }
    return ret;
}
int res;
void dfs_main(int cur){
    res += calc(cur,0);
    vis[cur] = true;
    for(int j = head[bal]; j; j = nxt[j]){
        int now = to[j];
        if(!vis[now]){
            res -= calc(now,len[j]);
            mic = 0x3f3f3f3f;
            getbal(now,cur,siz[now]);
            dfs_main(bal);
        }
    }
}
void solve(){
    res = 0;
    mic = 0x3f3f3f3f;
    getbal(1,0,N);
    dfs_main(bal);
    printf("%d\n",res);
}

int main(){
    input();
    solve();
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

#include <stack>

#include <cmath>

#include <map>

#include <complex>

using namespace std;

const int MAXV = 40005;

const int MAXE = 80005;

int N,M,K;

int head[MAXV],nxt[MAXE],to[MAXE],len[MAXE],vis[MAXV],gphtot;

void gph_init(){

gphtot = 2;

memset(head,0,sizeof(head));

memset(vis,0,sizeof(vis));

}

void gph_addEdge(int from,int _to,int cost){

to[gphtot] = _to;

nxt[gphtot] = head[from];

len[gphtot] = cost;

head[from] = gphtot++;

}

void input(){

scanf(" %d %d",&N,&M);

gph_init();

for(int i = 1; i <= M; i++){

int a,b,c;

char d;

scanf(" %d %d %d %c",&a,&b,&c,&d);

gph_addEdge(a,b,c);

gph_addEdge(b,a,c);

}

scanf(" %d",&K);

}

int siz[MAXV],mic,bal;

void getbal(int cur,int par,int totsiz){

int mxc = 0;

siz[cur] = 1;

for(int j = head[cur]; j; j = nxt[j]){

int now = to[j];

if(now != par && !vis[now]){

getbal(now,cur,totsiz);

siz[cur] += siz[now];

mxc = max(mxc,siz[now]);

}

mxc = max(mxc,totsiz - siz[cur]);

if(mic > mxc){

mic = mxc;

bal = cur;

}

int dis[MAXV],distot;

void dfs_dis(int cur,int par,int hav = 0){

dis[distot++] = hav;

siz[cur] = 1;

for(int j = head[cur]; j; j = nxt[j]){

int now = to[j];

if(now != par && !vis[now]){

dfs_dis(now,cur,hav+len[j]);

siz[cur] += siz[now];

}

int calc(int rt,int k){

distot = 0;

dfs_dis(rt,0,k);

int ret = 0;

sort(dis,dis+distot);

int r = distot - 1;

for(int l = 0; l < distot; l++){

while(dis[r] + dis[l] > K){

r--;

}

if(r <= l){

break;

}

ret += r-l;

}

return ret;

}

int res;

void dfs_main(int cur){

res += calc(cur,0);

vis[cur] = true;

for(int j = head[bal]; j; j = nxt[j]){

int now = to[j];

if(!vis[now]){

res -= calc(now,len[j]);

mic = 0x3f3f3f3f;

getbal(now,cur,siz[now]);

dfs_main(bal);

}

void solve(){

res = 0;

mic = 0x3f3f3f3f;

getbal(1,0,N);

dfs_main(bal);

printf("%d\n",res);

}

int main(){

input();

solve();

}

POJ 3107 Godfather

December 06, 20152015-12-06hahaschoolLeave a comment

题意

变相考察树的重心。

思路

请参考这个题和／或这个题

代码

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <set>
#include <stack>
#include <cmath>
#include <map>
#include <complex>

using namespace std;

const int MAXV = 50005;
const int MAXE = 100005;

struct Graph {
    int siz[MAXV];
    int dp[MAXV];
    int par[MAXV];

    int head[MAXV];
    int nxt[MAXE];
    int end[MAXE];
    int tot;
    void init() {
        memset(head,0,sizeof(head));
        tot = 2;
    }
    void addEdge(int from,int to) {
        end[tot] = to;
        nxt[tot] = head[from];
        head[from] = tot++;
    }
} gph;

int n;

void dfs(int cur,int par) {
    gph.par[cur] = par;
    gph.siz[cur] = 1;
    gph.dp[cur] = 1;
    for(int j = gph.head[cur]; j; j = gph.nxt[j]) {
        int now = gph.end[j];
        if(now != par) {
            dfs(now,cur);
            gph.siz[cur] += gph.siz[now];
            gph.dp[cur] = max(gph.siz[now],gph.dp[cur]);
        }
    }
}


vector<int> res;
int balance() {
    dfs(1,0);
    int ret = -1;
    for(int i = 1; i <= n; i++) {
        int dpn = max(gph.dp[i],n-gph.siz[i]);
        if(dpn <= n/2) {
            res.push_back(i);
            ret = 0;
        }
    }
    return ret;
}



int main() {
    scanf(" %d",&n);
    gph.init();
    for(int i = 1; i < n ; i++) {
        int a,b;
        scanf(" %d %d",&a,&b);
        gph.addEdge(a,b);
        gph.addEdge(b,a);
    }
    balance();
    for(int i = 0; i < res.size(); i++){
        printf("%d",res[i]);
        if(i == res.size()-1){
            puts("");
        }else{
            putchar(' ');
        }
    }
    return 0;
}

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

#include <stack>

#include <cmath>

#include <map>

#include <complex>

using namespace std;

const int MAXV = 50005;

const int MAXE = 100005;

struct Graph {

int siz[MAXV];

int dp[MAXV];

int par[MAXV];

int head[MAXV];

int nxt[MAXE];

int end[MAXE];

int tot;

void init() {

memset(head,0,sizeof(head));

tot = 2;

}

void addEdge(int from,int to) {

end[tot] = to;

nxt[tot] = head[from];

head[from] = tot++;

}

} gph;

int n;

void dfs(int cur,int par) {

gph.par[cur] = par;

gph.siz[cur] = 1;

gph.dp[cur] = 1;

for(int j = gph.head[cur]; j; j = gph.nxt[j]) {

int now = gph.end[j];

if(now != par) {

dfs(now,cur);

gph.siz[cur] += gph.siz[now];

gph.dp[cur] = max(gph.siz[now],gph.dp[cur]);

}

vector<int> res;

int balance() {

dfs(1,0);

int ret = -1;

for(int i = 1; i <= n; i++) {

int dpn = max(gph.dp[i],n-gph.siz[i]);

if(dpn <= n/2) {

res.push_back(i);

ret = 0;

}

return ret;

}

int main() {

scanf(" %d",&n);

gph.init();

for(int i = 1; i < n ; i++) {

int a,b;

scanf(" %d %d",&a,&b);

gph.addEdge(a,b);

gph.addEdge(b,a);

}

balance();

for(int i = 0; i < res.size(); i++){

printf("%d",res[i]);

if(i == res.size()-1){

puts("");

}else{

putchar(' ');

}

return 0;

}