标签 枚举 下的文章

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

tag:
动态规划，枚举，背包DP

思路：
用 f[i][j] 表示用前i块多米诺骨牌形成的差值为j时旋转次数。因为差值的范围是-5000-5000，所以数组加一个5000的偏移量。状态转移方程为 f[i][j + p] = min(f[i - 1][j - (a[i] - b[i]) + p], f[i - 1][j - (b[i] - a[i]) + p] + 1); 。 j - (a[i] - b[i]) + p 表示未加上第i块多米诺骨牌时的差值。上下旋转时，当前的差值会反过来，同时次数也要加一。最后求答案值，求绝对值从小到大第一个合法的值就是答案（正负都合法的话取一个最小值），表示差值最小时的旋转次数。

代码：

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1010, p = 5000;
int f[N][N * 6 * 2];
int a[N], b[N];
int n;
int main()
{
    memset(f, 0x3f, sizeof f);
    cin >> n;
    for (int i = 1; i <= n; i ++) cin >> a[i] >> b[i];
    f[1][0 + p + a[1] - b[1]] = 0, f[1][0 + p + b[1] - a[1]] = 1;
    if (a[1] == b[1]) f[1][p] = 0;
    for (int i = 2; i <= n; i ++)
    {
        for (int j = -5000; j <= 5000; j ++)
        {
            f[i][j + p] = min(f[i - 1][j - (a[i] - b[i]) + p], f[i - 1][j - (b[i] - a[i]) + p] + 1);
        }
    }
    int res = 0x3f3f3f3f;
    for (int i = 0; i <= 5000; i ++)
    {
        if (f[n][i + p] <= 1000 || f[n][-i + p] <= 1000)
        {
            res = min(f[n][i + p], f[n][-i + p]);
            break;
        }
    }
    cout << res << endl;
    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;
}

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

tag:
图论，枚举，最短路

思路：
这道题可以用floyd算法来做，每次询问，都将当前这个时间可以重建完的村庄用floyd算法更新一下所有点的最短路。最后判断一下这个询问的两个村庄是否重建完以及是否可以联通，如果重建完并且联通就输出最短路，否则输出-1

代码：

#include <iostream>
#include <vector>
using namespace std;
const int N = 220;
int n, m, q;
int f[N][N];
int a[N];

inline void update(int k)
{
    for (int i = 0; i < n; i ++)
        for (int j = 0;  j< n; j ++)
            f[i][j] = f[j][i] = min(f[i][j], f[i][k] + f[k][j]);
}
int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i ++) cin >> a[i];
    for (int i = 0; i < n; i ++)
    {
        for (int j = 0; j < n; j ++) f[i][j] = 0x3f3f3f3f;
        f[i][i] = 0;
    }
    for (int i = 0; i < m; i ++)
    {
        int x, b, w;
        cin >> x >> b >> w;
        f[x][b] = f[b][x] = w;
    }
    cin >> q;
    int idx = 0;
    for (int i = 0; i < q; i ++)
    {
        int x, y, z;
        cin >> x >> y >> z;
        while (a[idx] <= z && idx < n)
        {
            update(idx);
            idx ++;
        }
        if (a[x] > z || a[y] > z) cout << -1 << endl;
        else if (f[x][y] == 0x3f3f3f3f) cout << -1 << endl;
        else cout << f[x][y] << 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;
}
  1. 1
  2. 2