第五届新疆ACM H-虚无的后缀

来源

第五届新疆省ACM-ICPC程序设计竞赛nowcoder重现赛

H-虚无的后缀

思路1

好菜哦。

首先后缀零的个数最多，我们只需要考虑他的质因子2和5的个数就行了(存为a,b)。

因为其他因子对10没有贡献。

问题转化为：n个数对\((a,b)\)，选出k个数对使得\(min(tot_a,tot_b)\)最大

由于规模很小，\(tot_b最大6000\)我们可以\(f[i][j]选i个tot_b有j\)个进行背包

dp复杂度有点高\(O(n^3log_{5}10^{18})\)

思路2

还有一种就是贪心。

正着不行倒着贪。

每次取影响当前答案最小的删去，删n-k个

dp复杂度\(O(n^2)\)

sol1代码

#include <bits/stdc++.h>

#define ll long long

using namespace std;

const int N = 233;

ll read() {ll x; cin >> x; return x;}

int n, K, w[N], v[N], f[201][6007];

int main() {

    n = read(), K = read();

    for (int i = 1; i <= n; ++i) {

        ll x = read(), val;

        val = x;

        while(val % 5 == 0 && val) val /= 5, w[i]++;

        val = x;

        while(val % 2 == 0 && val) val /= 2, v[i]++;

    }

    memset(f, -0x3f, sizeof(f));

    f[0][0] = 0;

    for (int i = 1; i <= n; ++i) {

        for (int j = K; j >= 1; --j) {

            for (int k = 6000; k >= w[i]; --k) {

                f[j][k] = max(f[j][k], f[j - 1][k - w[i]] + v[i]);

            }

        }

    }

    int ans = 0;

    for (int i = 1; i <= 6000; ++i) {

        ans = max(ans, min(i, f[K][i]));

    }

    printf("%d\n", ans);

    return 0;

}

sol2代码

#include <bits/stdc++.h>

#define ll long long

using namespace std;

const int N = 233;

ll read() {ll x; cin >> x; return x;}

int n, K, w[N], v[N], vis[N], sum_2, sum_5;

int main() {

    n = read(), K = read();

    for (int i = 1; i <= n; ++i) {

        ll x = read(), val;

        val = x;

        while(val % 2 == 0 && val) val /= 2, v[i]++;

        val = x;

        while(val % 5 == 0 && val) val /= 5, w[i]++;

        sum_2 += v[i], sum_5 += w[i];

    }

    for (int i = 1; i <= n - K; ++i) {

        int mi = 0, id = 0;

        for (int j = 1; j <= n; ++j) {

            if (!vis[j] && mi < min(sum_2 - v[j], sum_5 - w[j]))

                mi = min(sum_2 - v[j], sum_5 - w[j]), id = j;

        }

        vis[id] = 1, sum_2 -= v[id], sum_5 -= w[id];

    }

    printf("%d\n", min(sum_2, sum_5));

    return 0;

}