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

tag:
SCOI2008，动态规划，搜索，记忆化搜索

思路：
开一个6维的数组来表示状态（因为每种情况有多种，所以不能用压位bit），分别表示足够涂1， 2， 3， 4， 5块木头的颜色有几种，最后一维表示上一种颜色的种类。然后用记忆化搜索来做。参考： https://www.luogu.com.cn/article/fhusu9wq

代码：

#include <iostream>
#include <cstring>
using namespace std;
typedef long long ll;
ll MOD = 1e9 + 7;
int n, t[6];
ll dp[16][16][16][16][16][6];
ll dfs(int a, int b, int c, int d, int e, int last)
{
    if (dp[a][b][c][d][e][last] != -1) return dp[a][b][c][d][e][last];
    if (a + b + c + d + e == 0) return 1;
    ll res = 0;
    if (a) res += (a - (last == 2)) * dfs(a - 1, b, c, d, e, 1);
    if (b) res += (b - (last == 3)) * dfs(a + 1, b - 1, c, d, e, 2);
    if (c) res += (c - (last == 4)) * dfs(a, b + 1, c - 1, d, e, 3);
    if (d) res += (d - (last == 5)) * dfs(a, b, c + 1, d - 1, e, 4);
    if (e) res += e * dfs(a, b, c, d + 1, e - 1, 5);
    dp[a][b][c][d][e][last] = res % MOD;
    return dp[a][b][c][d][e][last];
}
int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++)
    {
        int a;
        cin >> a;
        t[a] ++;
    }
    memset(dp, -1, sizeof dp);
    ll ans = dfs(t[1], t[2], t[3], t[4], t[5], 0);
    cout << ans << endl;
    return 0;
}

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

tag:
记忆化搜索，状压DP

思路：
记忆化搜索，dfs两个参数一个是当前的字母，另外一个是当前的状态。f[x, y] 表示当以字符串x开头是状态为y时最大的字符串长度。

代码：

#include <iostream>
#include <vector>
using namespace std;
string st[18];
vector<int> v[210];
int f[17][1 << 17];
int n, ans;
int dfs(int x, int y)
{
    if (f[x][y]) return f[x][y];
    int res = 0;
    for (auto i : v[st[x][st[x].size() - 1]])
        if (!((y>>(i - 1) & 1))) res = max(res, dfs(i, y | 1 << (i - 1)));
    return f[x][y] = res + st[x].size();
}
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++) cin >> st[i], v[st[i][0]].push_back(i);
    for (int i = 1; i <= n; i ++) ans = max(ans, dfs(i, (1 << (i - 1))));
    cout << ans << endl;
    return 0;
}

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

tag:
USACO09DEC，最短路，排序，USACO，2009

思路：
多次询问，点的数据范围小，所以可以用floyd，如果没有点权，那么这道题就是经典的多源汇最短路。为了处理这个点权，我们可以将每一个节点按照点权的大小从小到大排序，然后对于每一个中间节点都是按照从小到大来遍历，这样计算点权的时候，每次中间节点k一定是最大的，所以求点权的最大值时，只要在i，j，k也就是起点终点和用来更新的中间节点之间选择一个较大的即可。

代码：

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 300;
int n, m, q;
int ans[N][N], dist[N][N];
struct node {
    int val, idx;
} Node[N];
bool cmp (node &a, node &b)
{
    return a.val < b.val;
}
int main()
{
    cin >> n >> m >> q;
    for (int i = 1; i <= n; i ++)
    {
        cin >> Node[i].val;
        Node[i].idx = i;
    }
    sort(Node + 1, Node + n + 1, cmp);
    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= n; j ++)
            dist[i][j] = (i == j) ? 0 : 0x3f3f3f3f;
    memset(ans, 0x3f, sizeof ans);
    for (int i = 1; i <= m;  i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        dist[u][v] = dist[v][u] = min(dist[v][u], w);
    }
    for (int k = 1; k <= n; k ++)
        for (int i = 1; i <= n; i ++)
            for (int j = 1; j <= n; j ++)
            {
                dist[Node[i].idx][Node[j].idx] = min(dist[Node[i].idx][Node[j].idx], dist[Node[i].idx][Node[k].idx] + dist[Node[k].idx][Node[j].idx]);
                ans[Node[i].idx][Node[j].idx] = min(ans[Node[i].idx][Node[j].idx], dist[Node[i].idx][Node[j].idx] + max({Node[i].val, Node[j].val, Node[k].val}));
            }
    while (q --)
    {
        int a, b;
        cin >> a >> b;
        cout << ans[a][b] << endl;
    }
    return 0;
}

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

tag:
USACO14DEC，最短路，bfs，USACO，2014

思路：
求三遍最短路，分别是正着求Bessie 和 Elsie 到每个点的最短路，和逆着求终点n到每个点的最短路，然后枚举看从哪个点开始一起走（Bessie 可以背着 Elsie 走）然后到终点的能量最小，更新ans。最后输出ans即可。

代码：

#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
typedef pair<int, int> PII;
const int N = 1e5 + 10;
int B, E, P, n, m;
int idx, e[N], ne[N], h[N], w[N];
int distB[N], distE[N], distP[N];
bool st[N];
void add(int a, int b)
{
    e[idx] = b;
    ne[idx] = h[a];
    w[idx] = 1;
    h[a] = idx ++;
}
void dijkstra(int s, int dist[])
{
    memset(st, 0, sizeof st);
    dist[s] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0, s});

    while (!heap.empty())
    {
        auto t = heap.top();
        heap.pop();
        int ver = t.second;
        if (st[ver]) continue;
        st[ver] = true;
        for (int i = h[ver]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[ver] + w[i])
            {
                dist[j] = dist[ver] + w[i];
                heap.push({dist[j], j});
            }
        }
    }
}

int main()
{
    memset(h, -1, sizeof h);
    memset(distE, 0x3f, sizeof distE);
    memset(distB, 0x3f, sizeof distB);
    memset(distP, 0x3f, sizeof distP);
    cin >> B >> E >> P >> n >> m;
    for (int i = 0; i < m; i ++)
    {
        int a, b;
        cin >> a >> b;
        add(a, b), add(b, a);
    }
    dijkstra(1, distB);
    dijkstra(2, distE);
    dijkstra(n, distP);
    int ans = 0x3f3f3f3f;
    for (int i = 1; i <= n; i ++)
    {
        ans = min(ans, B * distB[i] + E * distE[i] + P * distP[i]);
    }
    cout << ans;
    return 0;
}

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

tag:
枚举，搜索，剪枝，dfs

思路：
先从大到小排序，并计算全部木棍长度的和。之后从最长的木棍长开始一直到和的一半枚举，作为原来木棍的长度。然后拿到这个原来的长度之后dfs一下看在有限段的情况下能不能拼凑出全部木棍，可以就输出。最后枚举完全部可能结果后都没答案，就输出长度和作为结果，表示原来只有一根木棍。参考： https://www.luogu.com.cn/article/fxoshw2y

代码：

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 70;
int n, len, m, sum;
int a[N];
int nxt[N];
bool flag = false;
bool st[N];
bool cmp (int &a, int &b)
{
    return a > b;
}
void dfs(int k, int last, int rest)
{
    int i;
    if (!rest) {
        if (k == m)
        {
            flag = true;
            return;
        }
        for (i = 0; i < n; i ++) if (!st[i]) break;
        st[i] = true;
        dfs(k + 1, i, len - a[i]);
        st[i] = false;
        if (flag) return;
    }
    int l = last + 1, r = n - 1;
    while (l < r)
    {
        int mid = (l + r) >> 1;
        if (a[mid] <= rest) r = mid;
        else l = mid + 1;
    }
    for (i = l; i < n; i ++)
    {
        if (!st[i])
        {
            st[i] = true;
            dfs(k, i, rest - a[i]);
            st[i] = false;
            if (flag) return;

            if (rest == a[i] || rest == len) return;
            i = nxt[i];
            if (i == n - 1) return;
        }
    }
}
int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++)
    {
        cin >> a[i];
        sum += a[i];
    }
    sort(a, a + n, cmp);
    nxt[n - 1] = n;
    for (int i = n - 2; i >= 0; i --)
    {
        if (a [i] == a[i + 1]) nxt[i] = nxt[i + 1];
        else nxt[i] = i;
    }
    for (len = a[0]; len <= sum / 2; len ++)
    {
        if (sum % len != 0) continue;
        m = sum / len;
        st[0] = true;
        dfs(1, 0, len - a[0]);
        st[0] = false;
        if (flag)
        {
            cout << len << endl;
            return 0;
        }
    }
    cout << sum << endl;
    return 0;
}