有限制的选择问题 <==> 背包

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 201;
int dp[N][25*N]; // dp[i][j][k] 第i个物品 恰好选了j个数 5的个数为k => 2的个数的最大值 --> 是一个二维费用背包问题
int main(){
    int n, m; cin>>n>>m;
    memset(dp, -0x3f, sizeof dp);
    dp[0][0]=0;
    for(int i=1;i<=n;i++){
        int v=0, w=0;
        LL x; cin>>x;
        while(x%2==0) x/=2, v++;
        while(x%5==0) x/=5, w++;
        for(int j=m;j>=1;j--){
            for(int k=25*i;k>=w;k--){
                dp[j][k]=max(dp[j][k], dp[j-1][k-w]+v);
            }
        }
    }
    int ans=0;
    for(int i=0;i<25*N;i++){
        ans=max(ans, min(i, dp[m][i]));
    }
    cout<<ans<<endl;
    return 0;
}