Submission #110392

#	Time	Username	Problem	Language	Result	Execution time	Memory
110392		pamaj	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	0 / 100	3 ms	384 KiB

joi2019_ho_t3

#include <bits/stdc++.h>
using namespace std;
const int maxn = 410;

int n;

bool check(string t)
{
	for(int i = 0; i < t.size(); i++)
		if(t[i] == t[i + 1]) return false;

	return true;
}

map<pair<int, string>, int> dp;

int solve(int num, string s)
{
	if(check(s)) return dp[{num, s}] = num;

	if(dp[{num, s}]) return dp[{num, s}];

	int melhor = 1e9;

	if(num == n) return 1e9;

	for(int i = 0; i < n - 1; i++)
	{
		string temp = s;

		swap(temp[i], temp[i + 1]);

		melhor = min(melhor, solve(num + 1, temp));
	}

	return dp[{num, s}] = melhor;
}

int main()
{
	cin >> n;

	string s;

	cin >> s;

	string t = s;

	sort(s.begin(), s.end());

	int ans = 1e9;

	do
	{
		if(check(s))
		{
			int num_dif = 0;

			for(int i = 0; i < n; i++)
				if(s[i] != t[i]) num_dif++;

			ans = min(ans, num_dif);
		} 
	} while(next_permutation(s.begin(), s.end()));

	//int ans = solve(0, s);

	cout << (ans == (int)1e9 ? -1 : ans) << "\n";

}

Compilation message (stderr)

joi2019_ho_t3.cpp: In function 'bool check(std::__cxx11::string)':
joi2019_ho_t3.cpp:9:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < t.size(); i++)
                 ~~^~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 55
• Subtask 3: 0 / 15
• Subtask 4: 0 / 25