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/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;
}

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

tag:
动态规划

思路：
问题1就是求最长下降子序列。问题2可以用c[i] 来表示以i为结尾长度为f[i] 的所有下降子序列，然后属性是数量。他可以由倒数第二个数的情况来转移，初始化是当长度为1时数量为1，之后遍历j从1到i，如果满足长度比f[j]大1，然后d[j] > d[i]，就说明可以由c[j] 转移过来，就让c[i] += c[j]，如果长度相同且大小相同，说明之前被计算过了，就让c[i] = 0，最后求答案时判断长度是否为最长，即答案1，如果为最长，则让res2 += c[i]。

代码：

#include <unordered_set>
#include <iostream>
using namespace std;
const int N = 5050;
int d[N], f[N], c[N];
int n, res1, res2;
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++) cin >> d[i];
    for (int i = 1; i <= n; i ++)
    {
        f[i] = 1;
        for (int j = 1; j < i; j ++)
        {
            if (d[j] > d[i]) f[i] = max(f[i], f[j] + 1);
        }
        res1 = max(res1, f[i]);
    }
    for (int i = 1; i <= n; i ++)
    {
        if (f[i] == 1) c[i] = 1;
        for (int j = 1; j < i; j ++)
        {
            if (f[i] == f[j] + 1 && d[j] > d[i]) c[i] += c[j];
            if (f[i] == f[j] && d[j] == d[i]) c[i] = 0;
        }
        if (f[i] == res1) res2 += c[i];
    }
    cout << res1 << ' ' << res2 << endl;
    return 0;
}

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

tag:
枚举，构造，动态规划

思路：
看了题解好像是可以用动态规划中的求最大子矩阵来做，但是这里用了很暴力的写法，加上前缀和优化也能过。这个做法本质上就是不断地枚举每一个矩形然后判断四条边是不是满足条件，然后再更新最大值就好了。

代码：

#include <iostream>
using namespace std;
const int N = 220;
int n, m;
int d[N][N], s[N][N], col[N][N];
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= m; j ++)
        {
            char c;
            cin >> c;
            if (c == '.') d[i][j] ++;
            s[i][j] = s[i][j - 1] + d[i][j];
            col[i][j] = col[i - 1][j] + d[i][j];
        }

    int res = 0;
    for (int i = 1; i <= n; i ++)
        for (int j = i; j <= n; j ++)
        {
            for (int k = 1; k <= m; k ++)
            {
                for (int l = k; l <= m; l ++)
                {
                    if (
                            col[j][k] - col[i - 1][k] == j - i + 1
                            && col[j][l] - col[i - 1][l] == j - i + 1
                            && s[i][l] - s[i][k - 1]  == l - k + 1
                            && s[j][l] - s[j][k - 1] == l - k + 1)
                        res = max(res, (j - i + 1) * (l - k + 1));
                }
            }
        }
    cout << res << endl;
    return 0;
}

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

tag：
最大子数列，Kadane 算法，动态规划

思路：
使用动态规划得方法来求解，用两个变量currentSum，和maxSum，分别来维护以当前位置结尾的最大子段和以及全局的最大子段和。状态转移分别是currentSum = max(a, currentSum + a), maxSum = max(maxSum, currentSum).最后输出maxSum即可。细节：一开始可以先定义为最小值-0x3f3f3f3f这样可以避免漏掉负数，以及因为要求和所以最好开long long避免爆int。

代码：

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int n;
int main()
{
    scanf("%d", &n);
    long long currentSum = -0x3f3f3f3f, maxSum = -0x3f3f3f3f;
    for (int i = 0; i < n; i ++)
    {
        long long a;
        scanf("%lld", &a);
        currentSum = max(a, currentSum + a);
        maxSum = max(maxSum, currentSum);
    }
    cout << maxSum << endl;
    return 0;
}