arius1408's blog

By arius1408, history, 4 weeks ago, In English

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

 
 
 
 
  • Vote: I like it
  • -21
  • Vote: I do not like it