What to do if you are stuck on a seemingly easy DP problem (or so I thought)
Well, I'm just doing some knapsack-DP problems and suddenly came to Problem 837D. At first I thought it's just a classic knapsack with some math stuff ... And here I'm writing this, so you know what happened. After I tried with the old type of transition (pick or left it) and still got test 1 wrong (the first test in the problem statement). I looked at the editorial and I think I got the recurrence formula (did I ?). Anyone can tell me why I keep on failing test 1. (Honestly I'm dying inside but pls help ..).
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 200, MaxP = 900;
int n, k;
ll dp[N][N][MaxP];
ll get2(ll x) { // get the number of 2s ...
ll s = 0;
while (x % 2 == 0) s++, x /= 2;
return s;
}
ll get5(ll x) { // get the number of 5s ...
ll s = 0;
while (x % 5 == 0) s++, x /= 5;
return s;
}
int main () {
scanf("%d%d", &n, &k);
for (int i = 1; i <= n; i++) {
ll x;
scanf("%lld", &x);
ll a = get2(x), b = get5(x);
for (int j = 1; j <= min(i, k); j++) {
for (int l = 0; l <= 900; l++) {
dp[i][j][l] = max(dp[i][j][l], dp[i-1][j][l]);
if (l-b >= 0)
dp[i][j][l] = max(dp[i][j][l], dp[i-1][j-1][l-b]+a);
}
}
}
ll ans = 0;
for (int i = 1; i <= n; i++)
for (int l = 0; l <= 900; l++)
ans = max(ans, min(1ll*l, dp[i][k][l]));
printf("%lld", ans);
}
P/S : this is just for testing , obviously even if my code work well, it will not get AC due to memory limit ..., but I'm failing such simple test