【POJ】3617 Best Cow Line(ディクショナリシーケンス文字列)

http://poj.org/problem?id=3617
長さN(1≦N≦2000)の文字列Sが与えられ、長さNの文字列Tが構築される.期首,Tは空欄であり,その後,以下の任意の操作を繰り返す.
Sのヘッダから1文字を削除し、Tの末尾に加算する
Sの末尾から1文字を削除し、Tの末尾に加算する
ディクショナリシーケンスをできるだけ小さくする文字列を作成することを目標としています
 
先頭と末尾の文字を比較して、等しい場合があるので注意して、等しい場合は等しくないまで中へ比較し続けます

#include 
#include 

using namespace std;

int main ()
{
	string str,c;
	int n,i;
	cin >> n;
	for(i=0;i> c;
		str += c;
	} 
	int a = 0;
	int b = n - 1;
	int ans = 0;
	while(a<=b)
	{
		bool flag = false;
		for(i=0;i+a<=b;i++)
		{
			if(str[a+i]str[b-i])
			{
				flag = false;
				break;
			}
		}
		if(flag)
			cout << str[a++];
		else
			cout << str[b--];
		ans++;
		if(ans==80)
		{
			cout << endl;
			ans = 0;
		}	
	}
	return 0;
} 

 
 
string+reverseで書くこともできます
一つ一つ比較する必要はなくstringの大きさで直接比較します

#include 
#include 
#include 

using namespace std;

int main ()
{
	int i,n;
	string s,c,t;
	cin >> n;
	for(i=0;i> c;
		s += c;
	}
	t = s;
	int ans = 0;
	while(s.length())
	{
		reverse(t.begin(),t.end());
		if(t>s)
		{
			cout << s[0];
			s.erase(0,1);
			t = s;
		}
		else
		{
			cout << t[0];
			t.erase(0,1);
			s = t;
		}
		ans++;
		if(ans==80)
		{
			cout << endl;
			ans = 0;
		}
	}
	return 0;
}