HDU-6778 Car 题解

题目大意

某市需要禁车，在五天中，每天可以对任意数量的尾号进行限制，但是每个尾号只能在五天内限制一次，问在所有方案中，五天内每天出来的车的最大值的最小值是多少。

解题思路

刚开始看到这个题目数据不大，就想到应该是爆搜的。

写完之后发现一直wa。。

以为是思路错了。

后面也没想到啥思路，其他的题目也写不出。

我太菜了。。

后面仔细看代码，自己想到应该是搜索的思路错了。

但是也没想到其他的方法。

看了大佬的代码，才知道正确的枚举思路。

说实话，搜索到现在都不是很会。。

其实就是把十种尾号枚举在五天中，总共应该是$5^{10}$。

跑完大概是900ms左右。

还需要多做题啊。。关于搜索的。

完整代码

#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
#include <cmath>
#include <stack>
#include <map>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <unordered_map>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

int cnt[10], num[10];
int n, ans;

template <typename T>
void read(T& x)
{
    int s = 0, c = getchar();
    x = 0;
    while (isspace(c))
        c = getchar();
    if (c == 45)
        s = 1, c = getchar();
    while (isdigit(c))
        x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
    if (s)
        x = -x;
}

void dfs(int x) {
    if (x == 10) {
        ans = min(ans, n - min(num[0], min(min(num[1], num[2]), min(num[3], num[4]))));
        return;
    }
    for (int i = 0; i < 5; i++) {
        num[i] += cnt[x];
        dfs(x + 1);
        num[i] -= cnt[x];
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int t;
    cin >> t;
    while (t--) {
        cin >> n;
        int l;
        memset(cnt, 0, sizeof(cnt));
        for (int i = 1; i <= n; i++) {
            cin >> l;
            cnt[l % 10]++;
        }
        ans = 1e9;
        dfs(0);
        cout << ans << endl;
    }
    return 0;
}