APP
题目链接：http://codeforces.com/contest/837/problem/D
题意： 给你n个数，让你任选K个，使得它们乘起来以后结尾的0最多。
解法：
将每个数的因子2和因子5的数量求出来，记作a[i]和b[i]。
答案就是max{ min{Σa[i]，Σb[i]} }（a[i]，b[i]是选择的那些数）。
暴力dp是f(i,j,k)表示前i个数，选j个，其中包含k个5的情况下，最多能包含多少个2。
转移是f(i,j,k)=max{ {f(t,j-1,k-b[i]}+a[i]}(1<=i<t) , f(i-1,j,k) }，时间是O(18 * n^3)，但空间存不下。
注意第二维为j时，只会从j-1或者j转移过来，所以可以滚动数组优化。
背包DP里面还有一种不用滚动数组优化的方式，就是逆着枚举，同样可以用到这里。
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个数其中有j个2最多有多少个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
