标签: 动态规划

[HDU4352]XHXJ’s LIS 题解

[HDU4352]XHXJ’s LIS 题解

题目地址:HDUOJ:Problem – 4352 题目描述 #define  

[POJ3734]Blocks 题解

[POJ3734]Blocks 题解

题目地址:POJ:3734 — Blocks

题目描述

Panda has received an assignment of painting a line of blocks. Since Panda is such an intelligent boy, he starts to think of a math problem of painting. Suppose there are N blocks in a line and each block can be paint red, blue, green or yellow. For some myterious reasons, Panda want both the number of red blocks and green blocks to be even numbers. Under such conditions, Panda wants to know the number of different ways to paint these blocks.
给一排砖块涂色,一共有红蓝绿黄4种颜色,要求最后红色和绿色砖块数一定是偶数,求合法的涂色方案数。

输入输出格式

输入格式:
The first line of the input contains an integer T(1≤T≤100), the number of test cases. Each of the next T lines contains an integer N(1≤N≤10^9) indicating the number of blocks.

输出格式:
For each test cases, output the number of ways to paint the blocks in a single line. Since the answer may be quite large, you have to module it by 10007.

输入输出样例

输入样例#1:

2
1
2

输出样例#1:

2
6

题解

我们用dp[i][0/1/2]表示涂到第i个砖块,当前红绿砖块分别全是奇数、一奇一偶、全是偶数时合法的方案数。我们可以通过下面的式子来转移。
\begin{matrix} dp[i][0] = 2dp[i - 1][0] + dp[i - 1][1] \\ dp[i][1] = 2dp[i - 1][0] + 2dp[i - 1][1] + 2dp[i - 1][2] \\ dp[i][2] = dp[i - 1][1] + 2dp[i - 1][2] \end{matrix}
我一看,人群裆中……不对,这个好像可以用矩阵来表示转移。表示出来是下面这个样子
\begin{pmatrix} dp[i][0] \\ dp[i][1] \\ dp[i][2] \end{pmatrix} = \begin{pmatrix} dp[i-1][0] \\ dp[i-1][1] \\ dp[i-1][2] \end{pmatrix} \times \begin{pmatrix} 2 & 1 & 0 \\ 2 & 2 & 2 \\ 0 & 1 & 2 \end{pmatrix}
那显然这个可以矩阵快速幂算一下,把后面那个转移矩阵n次方一下就好了。

代码

// Code by KSkun, 2018/3
#include <cstdio>
#include <cstring>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}

inline int readint() {
    register int res = 0, neg = 1;
    char c = fgc();
    while(c < '0' || c > '9') {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(c >= '0' && c <= '9') {
        res = res * 10 + c - '0';
        c = fgc();
    }
    return res * neg;
}

const int MO = 10007;

struct Matrix {
    int m[3][3];
};

inline void mul(Matrix &a, Matrix b) {
    Matrix res;
    memset(res.m, 0, sizeof(res.m));
    for(int i = 0; i < 3; i++) {
        for(int j = 0; j < 3; j++) {
            for(int k = 0; k < 3; k++) {
                res.m[i][j] += a.m[i][k] * b.m[k][j];
                res.m[i][j] %= MO;
            }
        }
    }
    a = res;
}

inline Matrix fpow(Matrix x, int k) {
    if(k == 1) return x;
    Matrix res = fpow(x, k >> 1);
    mul(res, res);
    if(k & 1) {
        mul(res, x);
    }
    return res;
}

int T, n;
Matrix mat, def;

inline void init() {
    memset(mat.m, 0, sizeof(mat.m));
    mat.m[0][0] = 2;
    mat.m[0][1] = 1;
    mat.m[1][0] = mat.m[1][1] = mat.m[1][2] = 2;
    mat.m[2][1] = 1;
    mat.m[2][2] = 2;
    memset(def.m, 0, sizeof(def.m));
    def.m[0][0] = def.m[1][1] = def.m[2][2] = 1;
}

int main() {
    T = readint();
    while(T--) {
        n = readint();
        init();
        mat = fpow(mat, n);
        mul(def, mat);
        printf("%d\n", def.m[0][0]);
    }
    return 0;
}
[APIO2014]序列分割 题解

[APIO2014]序列分割 题解

题目地址:洛谷:【P3648】[APIO2014]序列分割 – 洛谷、BZOJ 

[TopCoder12054]MaximalTriangle 题解

[TopCoder12054]MaximalTriangle 题解

题目地址:TopCoder Arena:Practice – TopCoder 

[HDU5181]numbers 题解

[HDU5181]numbers 题解

题目地址:HDUOJ:Problem – 5181

题目描述

Now you have a stack and n numbers 1,2,3,…,n. These n numbers are pushed in the order and popped if the number is at the top of the stack. You can read the sample to get more details.
This question is quite easy. Therefore I must give you some limits.
There are m limits, each is expressed as a pair <A,B> means the number A must be popped before B.
Could you tell me the number of ways that are legal in these limits?
I know the answer may be so large, so you can just tell me the answer mod 1000000007(10^9+7).
一个由1,2,…,n组成的排列,顺次插入栈中,你可以选择在任意时刻弹出栈顶元素,现在有m个要求,要求x必须在y之前出栈,问有多少种合法的出栈顺序。

输入输出格式

输入格式:
The first line contains an integer T(about 5),indicating the number of cases.
Each test case begins with two integers n(1≤n≤300) and m(1≤m≤90000).
Next m lines contains two integers A and B(1≤A≤n,1≤B≤n)
(P.S. there may be the same limits or contradict limits.)

输出格式:
For each case, output an integer means the answer mod 1000000007.

输入输出样例

输入样例#1:

5
1 0
5 0
3 2
1 2
2 3
3 2
2 1
2 3
3 3
1 2
2 3
3 1

输出样例#1:

1
42
1
2
0

说明

The only legal pop-sequence of case 3 is 1,2,3.
The legal pop-sequences of case 4 are 2,3,1 and 2,1,3.

题解

我们首先简化问题,不考虑限制,那我们设计状态dp[i][j]表示区间[i, j]内的方案数,枚举区间内最后一个弹出的元素k,那么有下面的方程
dp[i][j] = \sum_{k=i}^j (dp[i][k - 1] * dp[k + 1][j])
有了限制应该怎么办?我们先分析限制对我们转移的影响,假如有限制<A, B>:
如果A<B,包含[A, B]的区间[i, j],枚举的最后弹出元素为k在(A, B]之间时候显然成立,而如果出现A、B在k的同侧时这个问题会在更小的区间内被解决,不是我们现在考虑的。但是如果k=A时,A就比B晚弹出,这是显然不行的。结论:对于A<B的情况,k≠A。
如果A=B,这种条件并没办法成立,答案直接是0了。
如果A>B,包含[A, B]的区间[i, j],枚举的最后弹出元素为k不能在(B, A]内。

朴素地思考,我们可以枚举k的时候逐个条件判断一下。但是这样复杂度就成了O(n^3m),已经无法接受了。
那咋整啊?我们回头来看看一个限制对什么样的区间产生影响。这样的区间[i, j]肯定满足1 \leq i \leq \min(A, B), \max(A, B) \leq j \leq n。我们把区间的两个端点看成二维平面上的一个点,那么这个影响其实是对一个矩形产生的。对于给矩形打标记这种事情,自然可以使用二维差分处理。差分完了以后前缀和求一下,就能查单点了。我们开n个二维平面,枚举k来标记每个k在哪些区间里不能转移即可。这个题巧妙之处就在于把二维差分的思想用进去了。
最后的时间复杂度O(n^3+nm),空间复杂度O(n^3)

代码

// Code by KSkun, 2018/3
#include <cstdio>
#include <cstring>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1;
    char c = fgc();
    while(c < '0' || c > '9') {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(c >= '0' && c <= '9') {
        res = res * 10 + c - '0';
        c = fgc();
    }
    return res * neg;
}

const int MAXN = 305, MO = 1000000007;

int T, n, m, a, b;
LL dp[MAXN][MAXN];
int s[MAXN][MAXN][MAXN];

inline void add(int xa, int ya, int xb, int yb, int dimm) {
    s[xa][ya][dimm]++;
    s[xb + 1][yb + 1][dimm]++;
    s[xb + 1][ya][dimm]--;
    s[xa][yb + 1][dimm]--;
}

int main() {
    T = readint();
    while(T--) {
        memset(dp, 0, sizeof dp);
        memset(s, 0, sizeof s);
        n = readint();
        m = readint();
        bool flag = false;
        for(int i = 1; i <= m; i++) {
            a = readint();
            b = readint();
            if(a == b) flag = true;
            if(a < b) {
                add(1, b, a, n, a);
            } else {
                for(int j = b + 1; j <= a; j++) {
                    add(1, a, b, n, j);
                }
            }
        }
        if(flag) {
            printf("0\n");
            continue;
        }
        for(int k = 1; k <= n; k++) {
            for(int i = 1; i <= n; i++) {
                for(int j = 1; j <= n; j++) {
                    s[i][j][k] += s[i - 1][j][k] + s[i][j - 1][k] - s[i - 1][j - 1][k];
                }
            }
        }
        for(int i = 1; i <= n; i++) {
            dp[i][i] = dp[i][i - 1] = 1;
        }
        dp[n + 1][n] = 1;
        for(int len = 2; len <= n; len++) {
            for(int i = 1; i + len - 1 <= n; i++) {
                int j = i + len - 1;
                for(int k = i; k <= j; k++) {
                    if(!s[i][j][k]) {
                        dp[i][j] = (dp[i][j] + dp[i][k - 1] * dp[k + 1][j] % MO) % MO;
                    }
                }
            }
        }
        printf("%lld\n", dp[1][n]);
    }
    return 0;
}
[APIO2010]特别行动队 题解

[APIO2010]特别行动队 题解

题目地址:洛谷:【P3628】[APIO2010]特别行动队 – 洛谷、BZO 

[HNOI2008]玩具装箱 题解 & DP斜率优化原理与实现

[HNOI2008]玩具装箱 题解 & DP斜率优化原理与实现

题目地址:洛谷:【P3195】[HNOI2008]玩具装箱TOY – 洛谷、B 

[CF314E]Sereja and Squares 题解

[CF314E]Sereja and Squares 题解

题目地址:Codeforces:Problem – 314E – Codeforces、洛谷:【CF314E】Sereja and Squares – 洛谷

题目描述

Sereja painted n points on the plane, point number i (1 ≤ i ≤ n) has coordinates (i, 0). Then Sereja marked each point with a small or large English letter. Sereja don’t like letter “x”, so he didn’t use it to mark points. Sereja thinks that the points are marked beautifully if the following conditions holds:

  • all points can be divided into pairs so that each point will belong to exactly one pair;
  • in each pair the point with the lesser abscissa will be marked with a small English letter and the point with the larger abscissa will be marked with the same large English letter;
  • if we built a square on each pair, the pair’s points will be the square’s opposite points and the segment between them will be the square’s diagonal, then among the resulting squares there won’t be any intersecting or touching ones.

Little Petya erased some small and all large letters marking the points. Now Sereja wonders how many ways are there to return the removed letters so that the points were marked beautifully.
本来有一个由大小写字母组成的序列,序列满足以下条件:

  • 大小写字母两两都配对,配对指同一字母的大小写配对,且小写字母在左侧
  • 不能发现穿插的情况,例如abAB是不合法的,应该调整为aAbBabBA

现在所有的大写字母和部分小写字母被擦掉了,求恢复为一个满足上述序列的可行情况数量。

输入输出格式

输入格式:
The first line contains integer n the number of points (1 ≤ n ≤ 105). The second line contains a sequence consisting of n small English letters and question marks — the sequence of letters, that mark points, in order of increasing x-coordinate of points. Question marks denote the points without letters (Petya erased them). It is guaranteed that the input string doesn’t contain letter “x”.

输出格式:
In a single line print the answer to the problem modulo 4294967296. If there is no way to return the removed letters, print number 0.
Please, do not write the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.

输入输出样例

输入样例#1:

4
a???

输出样例#1:

20

输入样例#2:

4
abc?

输出样例#2:

0

输入样例#3:

6
abc???

输出样例#3:

1

题解

首先我们可以把小写字母看成左括号,大写字母看成右括号,这样就变成了求一个合法的括号序列的问题了。我们考虑使用动态规划。
令dp[i][j]表示处理到第i个字符,到现在还有j个左括号没有配对。分类转移:
如果i+1是左括号,把当前值加到dp[i+1][j+1]上。
如果i+1是问号,把当前值加到dp[i+1][j-1](如果i+1是右括号)和dp[i+1][j+1](如果i+1是左括号)上。
最后的答案就是dp[n][0]。
但是这么做的时间复杂度是O(n^2)的。因为i和j的上限都是n。

我们尝试换一种思路,用dp[i][j]表示处理到前i个,里面有j个右括号。只需要转移当前是问号的情况,填左括号dp[i][j]+=dp[i-1][j],填右括号dp[i][j]+=dp[i-1][j-1]。
最后的答案是dp[n][n/2]。
相比前一种想法,在这种想法中里面那层循环的规模会减小很多,这个可以感性的认识一下,因此我们大幅减小了常数,这个题就能过了。

等等,还没完!原题说用[a-wy-z]这个字符集里面的字母当做左括号来着,那么我们还要乘上25^{\frac{n}{2}-q}这个数字。q是题目固定的小写字母数量。因为每个左括号都可以有25种选择,右括号又是已经配对好的。到这里这个题就做完了。
对于取模,我们发现4294967296 = 2^{32},可以使用unsigned int的自然溢出来减小取模的常数。

代码

// Code by KSkun, 2018/3
#include <cstdio>

// variables

const int MAXN = 100005;

int n;
char str[MAXN];
unsigned int dp[MAXN];

// main

int main() {
    scanf("%d%s", &n, str + 1);
    if(n & 1) {
        printf("0");
        return 0;
    }
    dp[0] = 1;
    int cntl = 0, hn = n / 2;
    for(int i = 1; i <= n; i++) {
        if(str[i] == '?') {
            for(int j = i / 2; j && j >= i - hn; j--) {
                dp[j] += dp[j - 1];
            }
        } else {
            cntl++;
        }
    }
    unsigned int ans = dp[hn];
    for(int i = 1; i <= hn - cntl; i++) {
        ans *= 25;
    }
    printf("%u", ans);
    return 0;
}
[CQOI2009]叶子的染色 题解

[CQOI2009]叶子的染色 题解

题目地址:洛谷:【P3155】[CQOI2009]叶子的染色 – 洛谷、BZO