APP
題目鏈接：http://codeforces.com/contest/837/problem/D
題意：?給你n個(gè)數(shù)，讓你任選K個(gè)，使得它們乘起來以后結(jié)尾的0最多。
解法：
將每個(gè)數(shù)的因子2和因子5的數(shù)量求出來，記作a[i]和b[i]。
答案就是max{ min{Σa[i]，Σb[i]} }（a[i]，b[i]是選擇的那些數(shù)）。
暴力dp是f(i,j,k)表示前i個(gè)數(shù)，選j個(gè)，其中包含k個(gè)5的情況下，最多能包含多少個(gè)2。
轉(zhuǎn)移是f(i,j,k)=max{ {f(t,j-1,k-b[i]}+a[i]}(1<=i<t) , f(i-1,j,k) }，時(shí)間是O(18 * n^3)，但空間存不下。
注意第二維為j時(shí)，只會從j-1或者j轉(zhuǎn)移過來，所以可以滾動(dòng)數(shù)組優(yōu)化。
背包DP里面還有一種不用滾動(dòng)數(shù)組優(yōu)化的方式，就是逆著枚舉，同樣可以用到這里。
using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = 210;
typedef long long LL;
const int NN = 206*64;
int n, m;
LL a[maxn];
int dp[maxn][NN];
//dp[i][j]表示選i個(gè)數(shù)其中有j個(gè)2最多有多少個(gè)5
int ans;
int main()
{
while(~scanf("%d %d", &n,&m))
{
for(int i=1; i<=n; i++) scanf("%lld", &a[i]);
memset(dp, 0x80, sizeof(dp));
dp[0][0] = 0;
for(int i=1; i<=n; i++){
LL x1 = a[i], x2 = a[i];
int cnt2 = 0, cnt5 = 0;
while(x1%2==0) x1/=2, cnt2++;
while(x2%5==0) x2/=5, cnt5++;
for(int k=m; k>=1; k--){
for(int j=cnt2; j<NN; j++){
dp[k][j] = max(dp[k][j], dp[k-1][j-cnt2]+cnt5);
}
}
}
ans = 0;
for(int i=1; i<NN; i++){
ans = max(ans, min(dp[m][i], i));
}
printf("%d ", ans);
}
return 0;
}
本文摘自 ：https://blog.51cto.com/u
