| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
极限压内存,数组全用bool#include<iostream>
#include<stack>
#include<string.h>
#include<cmath>
#include<iomanip>
#include<algorithm>
#include<climits>
#include<cstdio>
#include<vector>
#include<sstream>
#include<ctype.h>
#include<set>
#include<map>
#include<ctime>
#include<stdlib.h>
#include<queue>
#include<bitset>
#define usi unsigned int
#define ull unsigned long long
using namespace std;
template<typename TTT>inline void mr(TTT& theNumberToRead)
{
theNumberToRead = 0;
bool prn = false;
char c = getchar();
while (!isdigit(c))
{
if (c == '-')prn = true;
c = getchar();
}
while (isdigit(c))
theNumberToRead = 10 * theNumberToRead + (c ^ 48), c = getchar();
if (prn)
theNumberToRead = -theNumberToRead;
}
template<typename TTT>inline TTT mrr()
{
TTT theNumberToRead = 0;
bool prn = false;
char c = getchar();
while (!isdigit(c))
{
if (c == '-')prn = true;
c = getchar();
}
while (isdigit(c))
theNumberToRead = 10 * theNumberToRead + (c ^ 48), c = getchar();
return prn ? -theNumberToRead : theNumberToRead;
}
template<typename T>void my_write(T x)
{
if (x)
my_write(x / 10),
putchar(x % 10 ^ 48);
}
template<typename T>void mw(T x, char mid)
{
if (x)
{
if (x < 0)
putchar('-'),
x = -x;
my_write(x);
}
else putchar(48);
if (mid)
putchar(mid);
}
// ******************************************华丽的分割线******************************************
// ******************************************华丽的分割线******************************************
// ******************************************华丽的分割线******************************************
// ******************************************华丽的分割线******************************************
// ******************************************华丽的分割线******************************************
int n;
bool a[5000], f[5000];
int solve(int k)
{
memset(f, 0, sizeof(f));
int res = 0;
bool sum = 0;
for (int i = 0; i + k <= n; ++i)
{
if (a[i] != sum)
++res, sum = !sum, f[i] = true;
if (i - k + 1 >= 0 && f[i - k + 1])
sum = !sum;
}
for (int i = n - k + 1; i < n; ++i)
{
if (a[i] != sum)
return INT_MAX;
if (i - k + 1 >= 0 && f[i - k + 1])
sum = !sum;
}
return res;
}
int main()
{
int ansK, ansM = INT_MAX;
mr(n);
for (int i = 0; i < n; ++i)
{
char c;
while (!isalpha(c = getchar()));
a[i] = c == 'B';
}
for (int k = 1, temp; k <= n; ++k)
{
temp = solve(k);
if (temp < ansM)
ansM = temp, ansK = k;
}
mw(ansK, ' ');
mw(ansM, '\n');
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator