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

tag:
NOI1999，dfs，剪枝，搜索

思路：
使用dfs和剪枝。dfs有四个参数，分别表示第几层，剩余体积，当前的面积，剩余层数。剪枝是有两个，第一个，如果当前的表面积加上之后最小的面积大于当前的面积，就return，第二个，之后最大的体积小于剩余的体积就return。边界情况是当剩余体积v小于0，return；当前层数超过m，return；当前的面积大于最小面积，return。终止条件是当剩余体积v == 0，然后层数等于m时表面积加上每层的上表面积（其实就是第一层蛋糕的顶层表面积），然后更新minv。考虑特殊情况，如果层数为1则直接遍历半径r，然后找到一个最小的表面积。

代码：

#include <iostream>
#include <cmath>
using namespace std;
int n, m, minv = 0x3f3f3f3f;
int r[20], h[20];
void dfs(int u, int v, int c, int p)
{
    if (v < 0) return;
    if (u > m + 1) return;
    if (c >= minv) return;

    if (v == 0 && u == m + 1)
    {
        c += r[1] * r[1];
        minv = min(minv, c);
        return;
    }

    if (c + p + r[1] * r[1] > minv) return;

    if (v - (r[u - 1] * r[u - 1] * h[u - 1] * p) > 0) return;

    for (int i = r[u - 1] - 1; i >= p; i--)
    {
        for (int j = h[u - 1] - 1; j >= p; j --)
        {
            if (v - i * i * j >= 0 && u + 1 <= m + 1)
            {
                r[u] = i;
                h[u] = j;

                dfs(u + 1, v - i * i * j, c + 2 * i * j, p - 1);

                r[u] = 0;
                h[u] = 0;
            }
        }
    }
}
int main()
{
    cin >> n >> m;
    if (m == 1)
    {
        for (int r = 1; r <= sqrt(n); r ++)
        {
            if (n % (r * r) == 0)
            {
                int h = n / (r * r);
                int tmp = 2 * r * h + r * r;
                minv = min(minv, tmp);
            }
        }
        if (minv == 0x3f3f3f3f) cout << 0;
        else cout << minv;
        return 0;
    }
    r[0] = (int)sqrt(n);
    h[0] = (int)sqrt(n);
    dfs(1, n, 0, m);
    if (minv == 0x3f3f3f3f) cout << 0;
    else cout << minv;
    return 0;
}

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

tag:
USACO05DEC，dfs，剪枝，搜索

思路：
先按照从大到小排序，然后计算前缀和。之后每次dfs，先判断上一个累加的结果有没有超过w，如果有就return，否则就更新res，然后判断是不是所有点都判断完了，如果是，则return。之后计算一下剩余的值之和，如果剩余的值之和加上当前累加的值比res小就直接return。否则就判断下一个值加上累加的值会不会超过w如果没有加加上那个值，然后递归dfs，最后再dfs没有加上这个值的情况。

代码：

#include <iostream>
#include <algorithm>
using namespace std;
long long n, w;
long long d[1010], sum[1010];
long long res = -1;
bool st[1010];
void dfs(int u, long long tmp)
{
    if (tmp > w) return;
    res = max(res, tmp);
    if (u == n) return;
    long long remain = sum[n] - sum[u];
    if (remain + tmp <= res) return;
    if (tmp + d[u + 1] <= w) dfs(u + 1, tmp + d[u + 1]);
    dfs(u + 1, tmp);

}
bool cmp (long long &a, long long &b)
{
    return a > b;
}
int main()
{
    cin >> n >> w;
    for (int i = 1; i <= n; i ++)
    {
        cin >> d[i];
    }
    sort(d + 1, d + 1 + n, cmp);
    for (int i = 1; i <= n; i ++) sum[i] = sum[i - 1] + d[i];
    dfs(0, 0);
    cout << res;
    return 0;
}

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

tag:
动态规划，状压DP，dfs，记忆化搜索

思路：
可以是状态压缩dp，也可以是用dfs加上记忆化搜索。这里就用dfs加上记忆化搜索。用二进制来存储每一种状态，每次访问一个点就将那个点异或一下。最后每次都是返回一个答案。dp中存的是从x点开始走走到最后一个点的最短路径。

代码：

#include <iostream>
#include <map>
#include <cmath>
using namespace std;
typedef pair<double, double> PII;
int n;
PII d[20];
bool st[20];
double dp[20][1 << 16];
double dfs(int x, int u, double step, int path)
{
    double res = 1e9;
    if (u == n)
    {
        return step;
    }
    if (dp[x][path]) return dp[x][path] + step;

    for (int i = 1; i <= n; i ++)
    {
        if (!st[i])
        {
            st[i] = true;
            double tmp = sqrt(pow(d[i].first - d[x].first, 2) + pow(d[i].second - d[x].second, 2));
            res = min(res, dfs(i, u + 1, step + tmp, path | (1 << i)));
            st[i] = false;
        }
    }

    dp[x][path] = res - step;
    return res;
}
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++) cin >> d[i].first >> d[i].second;
    double res = dfs(0, 0, 0.0, 0);
    printf("%.2lf", res);
    return 0;
}

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

tag:
NOIP2002 提高组，字符串，bfs

思路：
因为是求最少的变换次数，所以可以用bfs。每次搜索都遍历字符串的每一个位置，将可以替换的地方都替换，然后判断是否出现过，没有出现过就加入队列。最后第一次出现字符串b的时候步数就是答案。

代码：

#include <iostream>
#include <queue>
#include <map>
#include <unordered_set>
using namespace std;

typedef pair<string, string> PSS;
typedef pair<string, int> PSI;

PSS mp[6];
string a, b;
queue<PSI> q;
unordered_set<string> st;
int idx = 0;

int bfs()
{
    q.push({a, 0});
    st.insert(a);

    while (!q.empty())
    {
        auto [current, step] = q.front(); q.pop();

        if (current == b) return step;

        if (step >= 10) continue;

        for (int i = 0; i < idx; i++)
        {
            string from = mp[i].first;
            string to = mp[i].second;
            size_t pos = current.find(from);
            while (pos != string::npos)
            {
                string newstr = current.substr(0, pos) + to + current.substr(pos + from.size());
                if (newstr.size() <= 20)
                {
                    if (!st.count(newstr))
                    {
                        st.insert(newstr);
                        q.push({newstr, step + 1});
                    }
                }
                pos = current.find(from, pos + 1);
            }
        }
    }
    return -1;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> a >> b;
    string c, d;
    while (cin >> c >> d)
    {
        if (!c.empty() && idx < 6)
        {
            mp[idx++] = {c, d};
        }
    }
    int res = bfs();

    if (res != -1 && res <= 10)
        cout << res;
    else
        cout << "NO ANSWER!";

    return 0;
}

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

tag:
NOIP2015 普及组，贪心，线段树，树状数组，前缀和，动态规划。

思路：
思路都是用贪心的策略，有两种情况，一种是取前x个a最大的客户，第二种是取前x - 1个a最大的客户，然后再从第i到n个中选择距离最远的一个去替换第x个a最大的客户，两种情况取最大值输出即可。如何求呢？这里用动态规划和前缀和来求，具体可以看代码。看其他题解有用线段树来做，但是比较麻烦，就上动规和前缀和了。

代码：

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int n;
long long sum[N], c[N], h[N];
struct client {
    int s, a;
}Client[N];
bool cmp(client &a, client &b)
{
    return a.a > b.a;
}
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++) cin >> Client[i].s;
    for (int i = 1; i <= n; i ++) cin >> Client[i].a;
    sort(Client + 1, Client + 1 + n, cmp);
    for (int i = 1; i <= n; i ++)
    {
        sum[i] = sum[i - 1] + Client[i].a;
        h[i] = max(h[i - 1], (long long)Client[i].s * 2);
    }
    for (int i = n; i >= 1; i --)
    {
        c[i] = max(c[i + 1], 2LL * Client[i].s + Client[i].a);
    }
    for (int i = 1; i <= n; i ++)
    {
        cout << max(sum[i] + h[i], sum[i - 1] + c[i]) << '\n';
    }
    return 0;
}