url: https://www.luogu.com.cn/problem/CF149D

tag:
搜索，记忆化搜索，区间DP

思路：
使用 f[l][r][i][j] 表示区间l和r之间l为i色，r为j色时的染色方案数。有两种情况，当 l 和 r 配对时，可以由 l + 1 到 r - 1更新过来。如果不配对，由 l 到 第一个配对的括号这段区间和由那个括号后面的括号到 r 这段区间的方案数相乘。注意如果相邻的括号都有染色且颜色一样需要跳过。初始化是当 l + 1 == r 时，此时区间只有两个括号，对应的四个情况都只有一种方案。最后dfs之后将所有可能的答案相加并取模，然后输出即可。

代码：

#include <iostream>  
#include <cstdio>  
#include <cstring>  
#include <algorithm>  
#include <stack>  
using namespace std;  
const int N = 800;  
const int mod = 1000000007;  
char s[N];  
stack<int> stk;  
int rightt[N];  
int f[N][N][5][5];  
void dfs(int l, int r)  
{  
    if (l + 1 == r)  
    {  
        f[l][r][0][1] = f[l][r][0][2] = f[l][r][1][0] = f[l][r][2][0] = 1;  
        return;  
    }  
    if (r == rightt[l])  
    {  
        dfs(l + 1, r - 1);  
        for (int i = 0; i <= 2; i ++)  
            for (int j = 0; j <= 2; j ++)  
            {  
                if (j != 1) f[l][r][0][1] += f[l + 1][r - 1][i][j], f[l][r][0][1] %= mod;  
                if (j != 2) f[l][r][0][2] += f[l + 1][r - 1][i][j], f[l][r][0][2] %= mod;  
                if (i != 1) f[l][r][1][0] += f[l + 1][r - 1][i][j], f[l][r][1][0] %= mod;  
                if (i != 2) f[l][r][2][0] += f[l + 1][r - 1][i][j], f[l][r][2][0] %= mod;  
            }  
    }  
    else  
    {  
        dfs(l, rightt[l]), dfs(rightt[l] + 1, r);  
        for (int i = 0; i <= 2; i ++)  
            for (int j = 0; j <= 2; j ++)  
                for (int p = 0; p <= 2; p ++)  
                    for (int q= 0; q <= 2; q ++)  
                    {  
                        if (j == 1 && p == 1 || j == 2 && p == 2) continue;  
                        f[l][r][i][q] += (f[l][rightt[l]][i][j] * f[rightt[l] + 1][r][p][q] % mod);  
                        f[l][r][i][q] %= mod;  
                    }  
    }  
}  
int main() {  
    scanf("%s", s + 1);  
    int n = strlen(s + 1);  
    for (int i = 1; i <= n; i++)  
    {  
        if (s[i] == '(') stk.push(i);  
        else  
        {  
            rightt[i] = stk.top();  
            rightt[stk.top()] = i;  
            stk.pop();  
        }  
    }  
    dfs(1, n);  
    int res = 0;  
    for (int i = 0; i <= 2; i ++)  
        for (int j = 0; j <= 2; j ++)  
            res += f[1][n][i][j], res %= mod;  
    cout << res << endl;  
    return 0;  
}

url: https://www.luogu.com.cn/problem/P4170

tag:
字符串，动态规划，枚举，区间DP

思路：
使用 f[i][j] 表示从i到j这个区间中如果要涂到规定的情况，最少需要的涂色次数。因为有区间，所以可以使用区间DP，对于每一各区间i到j来说如果第i个字符和第j个字符相同，则 f[i][j] 可以从 f[i][j - 1] 更新过来。如果不相同，则可以枚举这个区间中的每一个位置，将这个区间变为两个区间分别进行，由两个区间进行更新。初始状态，每个长度为1的区间，要达到规定的情况只需要涂一次就行。最后输出 f[0][n - 1] 即可。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 60;
int f[N][N];
int main()
{
    char s[60];
    cin >> s;
    int n = strlen(s);
    for (int i = 0; i < n; i ++) f[i][i] = 1;
    for (int l = 1; l < n; l ++)
    {
        for (int i = 0; i + l < n;  i++)
        {
            if (s[i] == s[i + l]) f[i][i + l] = f[i][i + l - 1];
            else
            {
                f[i][i + l] = f[i][i] + f[i + 1][i + l];
                for (int k = i + 1; k < i + l; k ++)
                    f[i][i + l] = min(f[i][i + l], f[i][k] + f[k + 1][i + l]);
            }
        }
    }
    cout << f[0][n - 1] << endl;
    return 0;
}

url: https://www.luogu.com.cn/problem/P3205

tag:
动态规划，区间DP，2010

思路：
利用区间DP来做。设 f[i][j][0] 表示区间i到j中i从左边进入区间的情况， f[i][j][1] 表示区间i到j中j从右边进入区间的情况。当i从左边进去时，上一个区间应该是 i + 1 到 j ，所以只有当 h[i] < h[i + 1] 以及 h[i] < h[j] 时才能更新。同理当 h[j] > h[i] 以及 h[j] > h[j - 1] 时，j从右边进入区间，区间从 i 到 j - 1 更新到 i 到 j 。初始化为了避免当一个数字时有两种情况，所以可以是都假装是从左边进入区间，（或者是右边也行只要保证只保留一种情况就行）。最后答案将 f[1][n][0] 和 f[1][n][1] 两种情况相加后取模输出即可。

代码：

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 1010, mod = 19650827;
typedef long long LL;
int n;
int h[N];
LL f[N][N][2];
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++) cin >> h[i];
    for (int i = 1; i <= n; i ++) f[i][i][0] = 1;
    for (int len = 1; len <= n; len ++)
    {
        for (int i = 1, j = i + len; j <= n; i ++, j ++)
        {
            if (h[i] < h[i + 1]) f[i][j][0] += f[i + 1][j][0];
            if (h[i] < h[j]) f[i][j][0] += f[i + 1][j][1];
            if (h[j] > h[i]) f[i][j][1] += f[i][j - 1][0];
            if (h[j] > h[j - 1]) f[i][j][1] += f[i][j - 1][1];
            f[i][j][0] %= mod;
            f[i][j][1] %= mod;
        }
    }
    LL res = (f[1][n][0] + f[1][n][1]) % mod;
    cout << res << endl;
    return 0;
}

url: https://www.luogu.com.cn/problem/P1040

tag:
动态规划，递归，枚举，区间DP，NOIP提高组，2003

思路：
使用区间dp的思路，令 f[i][j] 为节点i到节点j之间最大的加分，并用 root[i][j] 记录下这段区间的根节点。之后遍历每一种可能的区间，依据题目的公式更新数组f记录root最后得出结果输出 f[1][n] 即表示给定的二叉树tree的最高加分。然后再输出该情况时树的前序遍历即可。

代码：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long LL;
const int N = 31;
int h[N], e[N * 2], ne[N * 2], idx;
int n;
LL f[N][N];
int root[N][N];
void print(int l ,int r)
{
    if (l > r) return;
    cout << root[l][r] << ' ';
    if (l == r) return;
    print(l, root[l][r] - 1),print(root[l][r] + 1, r);
}
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++) cin >> f[i][i], root[i][i] = i;
    for (int len = 1; len <= n; len ++)
        for (int i = 1; i + len <= n; i ++)
        {
            int j = i + len;
            f[i][j] = f[i + 1][j] + f[i][i];
            root[i][j] = i;
            for (int k = i + 1; k <= j; k ++)
            {
                if (f[i][j] < f[i][k - 1] * f[k + 1][j] + f[k][k])
                {
                    f[i][j] = f[i][k - 1] * f[k + 1][j] + f[k][k];
                    root[i][j] = k;
                }
            }
        }
    cout << f[1][n] << endl;
    print(1, n);
    return 0;
}