hubert322's blog

By hubert322, history, 8 years ago, In English

Can someone explain this runtime error? Here's my code: http://ideone.com/pCBf77 Thanks!

Full text and comments »

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

By hubert322, history, 8 years ago, In English

This is the question I'm dealing with: http://codeforces.com/problemset/problem/327/A

I'm trying to practice dynamic programming, and this is the code that I have came up.

#include <bits/stdc++.h>

using namespace std;

const int maxN = 100;

int a [maxN + 5], dp [maxN + 5];

int main ()
{
	int n;
	
	scanf ("%d", &n);
	
	int ans = 0;
	for (int i = 0; i < n; i++)
	{
		scanf ("%d", &a [i]);
		if (a [i] == 1)
			ans++; // get how many 1s are in the numbers
	}
	
	for (int i = 0; i < n; i++)
	{
		dp [i] = 0; // set to 0 since we're getting max
		for (int j = i; j < n; j++)
		{
			int count = 0;
			for (int k = i; k <= j; k++)
			{
				if (a [k] == 1)
					count -= a [k];
				else
					count += 1;
			} // basically, if we have more zero than ones, we would choose it.
			dp [i] = max (count, dp [i]);
		}
		if (i > 0)
			dp [i] = max (dp [i], dp [i - 1]);
	}
	if (ans == n)
		ans--;
	printf ("%d\n", ans + dp [n - 1]);
	
	return 0;
}

Though it got accepted, I feel like this isn't the efficient way? So, what is the correct way of doing such dp problem?

Full text and comments »

Tags dp
  • Vote: I like it
  • 0
  • Vote: I do not like it