https://www.luogu.com.cn/problem/CF837D
思路:
末尾为0的个数&＃xff0c;乘0是不会产生贡献的。
产生贡献的其实就是质因数分解2和5&＃xff0c;且乘下来0的个数由min(sum2,sum5)决定。
于是就成了暴力跑背包取0,5个数。
空间不够。所以要滚动数组。
#include#include#include#include#include#include#include#include#include#define debug(a) cout<<#a<<"&＃61;"<using namespace std;const int maxn&＃61;220;typedef long long LL;inline LL read(){LL x&＃61;0,f&＃61;1;char ch&＃61;getchar(); while (!isdigit(ch)){if (ch&＃61;&＃61;&＃39;-&＃39;) f&＃61;-1;ch&＃61;getchar();}while (isdigit(ch)){x&＃61;x*10&＃43;ch-48;ch&＃61;getchar();}return x*f;}LL num5[maxn],num2[maxn];LL dp[maxn][5050];void getnum5(LL x,LL i){while(x%5&＃61;&＃61;0){x/&＃61;5;num5[i]&＃43;&＃43;;}}void getnum2(LL x,LL i){while(x%2&＃61;&＃61;0){x/&＃61;2;num2[i]&＃43;&＃43;;}}int main(void){cin.tie(0);std::ios::sync_with_stdio(false);LL n,m;cin>>n>>m;LL x;for(LL i&＃61;1;i<&＃61;n;i&＃43;&＃43;){cin>>x;getnum5(x,i);getnum2(x,i);}memset(dp,-0x3f,sizeof(dp));dp[0][0]&＃61;0;for(LL i&＃61;1;i<&＃61;n;i&＃43;&＃43;){for(LL j&＃61;m;j>&＃61;1;j--){for(LL k&＃61;5000;k>&＃61;0;k--){if(k>&＃61;num5[i]){dp[j][k]&＃61;max(dp[j][k],dp[j-1][k-num5[i]]&＃43;num2[i]);}}}}LL ans&＃61;0;for(LL k&＃61;1;k<&＃61;5000;k&＃43;&＃43;){/// cout<return 0;}
京公网安备 11010802041100号