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/UVA1629

tag:
动态规划，枚举，前缀和

思路：
用 dp[lx][ly][rx][ry] 来记录某一个区间中，为使每一块蛋糕都有樱桃的最小代价。使用dfs来枚举每一种可能性。使用记忆化搜索来减少时间。前缀和快速计算出某一块区域樱桃的数量。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 30;
int dp[N][N][N][N];
int p[N][N];
int cs;
int pnum(int lx, int ly, int rx, int ry)
{
    return p[rx][ry] - p[lx - 1][ry] - p[rx][ly - 1] + p[lx - 1][ly - 1];
}
int DP(int lx, int ly, int rx, int ry)
{
    if (pnum(lx, ly, rx, ry) == 0) return 0x3f3f3f3f;
    if (pnum(lx, ly, rx, ry) == 1) return 0;
    int &d = dp[lx][ly][rx][ry];
    if (d != 0x3f3f3f3f) return d;
    for (int i = lx; i < rx; i ++)
        d = min(d, DP(lx, ly, i, ry) + DP(i + 1, ly, rx, ry) + ry - ly + 1);
    for (int i = ly; i < ry; i ++)
        d = min(d, DP(lx, ly, rx, i) + DP(lx, i + 1, rx, ry) + rx - lx + 1);
    return d;
}
int main()
{
    int n, m, k;
    while(scanf("%d%d%d", &n, &m, &k) != EOF && n && m)
    {
        memset(p, 0, sizeof p);
        for (int i = 0; i < k; i ++)
        {
            int a, b;
            scanf("%d%d", &a, &b);
            p[a][b] = 1;
        }
        for (int i = 1; i <= n; i ++)
            for (int j = 1; j <= m; j ++)
                p[i][j] += p[i - 1][j] + p[i][j - 1] - p[i - 1][j - 1];
        memset(dp, 0x3f, sizeof dp);
        printf("Case %d: %d\n", ++cs, DP(1, 1, n, m));
    }
    return 0;
}

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

tag:
动态规划，树形DP

思路：
用 tr[u][0/1] 来存二叉树。做两次dfs第一次求出最大的深度和最小的深度，如果相差大于1直接输出-1。第二次dfs从下到上递归，设计返回值为0/1/2分别表示都是浅层，都是深层和混合。当左边为浅层，右边为深层或者左边为混合，右边为深层时交换答案加1，如果存在某个节点两边都是混合的情况时说明无论怎么交换都不会改变当前的情况，则输出-1程序结束。最后如果存在一个方案使得可以交换成功就输出答案ans。

代码：

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 1e5 + 10;
int tr[N][2],ans, mi = 0x3f3f3f3f, mx;
int n;
void dfs1(int u, int dep)
{
    if (u == -1)
    {
        mi = min(mi, dep);
        mx = max(mx, dep);
        return;
    }
    dfs1(tr[u][0], dep + 1), dfs1(tr[u][1], dep + 1);
}
int dfs2(int u, int dep)
{
    if (u == -1) return (dep != mi);
    int x = dfs2(tr[u][0], dep + 1);
    int y = dfs2(tr[u][1], dep + 1);
    ans += (!x && y) || (x == 2 && y == 1);
    if (x == 2 && y == 2)
    {
        cout << -1;
        exit(0);
    }
    if (x + y == 1 || x == 2 || y == 2) return 2;
    if (!(x + y)) return 0;
    return 1;
}
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++) cin >> tr[i][0] >> tr[i][1];
    dfs1(1, 0);
    if (mx - mi > 1) cout << -1 << endl;
    else if (mi == mx) cout << 0 << endl;
    else
    {
        int _ = dfs2(1, 0);
        cout << ans << endl;
    }
    return 0;
}

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

tag:
动态规划，树形DP，背包DP

思路：
用 f[u][j] 表示第u个节点选择j个用户时的盈利数。使用分组背包的思想。状态转移方程为
f[u][k] = max(f[u][k], f[u][k - l] + f[j][l] - w[i]) 其中w表示如果将节点j接入时的成本。最后因为是求不亏本时最多可以观看转播的用户数，所以从m开始向下循环，直到找到第一个盈利大于等于0的然后输出用户数即可。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 3030;
int h[N], e[N * 2], ne[N * 2], w[N * 2], idx;
int n, m;
int p[N];
int s[N];
int f[N][N];
void dfs(int u, int fa)
{
    if (u > n - m) f[u][1] = p[u], s[u] = 1;
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (j == fa) continue;
        dfs(j, u);
        s[u] += s[j];
        for (int k = m; k >= 0; k --)
        {
            for (int l = 1; l <= min(k, s[j]); l ++)
            {
                f[u][k] = max(f[u][k], f[u][k - l] + f[j][l] - w[i]);
            }
        }
    }
}
void add(int a, int b, int c)
{
    e[idx] = b;
    ne[idx] = h[a];
    w[idx] = c;
    h[a] = idx ++;
}
int main()
{
    memset(h, -1, sizeof h);
    memset(f, -0x3f, sizeof f);
    cin >> n >> m;
    for (int i = 1; i <= n - m; i ++)
    {
        int k;
        cin >> k;
        for (int j = 0; j < k; j ++)
        {
            int a, b;
            cin >> a >> b;
            add(i, a, b), add(a, i, b);
        }
    }
    for (int i = n - m + 1; i <= n; i ++) cin >> p[i];
    for (int i = 1; i <= n; i ++) f[i][0] = 0;
    dfs(1, 0);
    for (int i = m; i >= 0; i --)
    {
        if (f[1][i] >= 0)
        {
            cout << i;
            break;
        }
    }
    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;
}