來源

第五屆新疆省ACM-ICPC程序設計競賽nowcoder重現(xiàn)賽
H-虛無的后綴

思路1

好菜哦。
首先后綴零的個數(shù)最多，我們只需要考慮他的質因子2和5的個數(shù)就行了(存為a,b)。
因為其他因子對10沒有貢獻。
問題轉化為：n個數(shù)對\((a,b)\)，選出k個數(shù)對使得\(min(tot_a,tot_b)\)最大
由于規(guī)模很小，\(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; }

轉載于:https://www.cnblogs.com/dsrdsr/p/10976681.html

總結

以上是生活随笔為你收集整理的第五届新疆ACM H-虚无的后缀的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。