[BOJ]1509号:ファリンドロン分割(C+)[GoldI]

10265 ワード
白駿 boj テキストリンク
問題に答える

Problem


  • は、ある文字列をファリンドロンの集合に分割できる数を尋ねる最初の問題である.
    間違えました.しかし、問題は、少なくともいくつかのファリンドロンで文字列を表すことができることです.
    文字列がABACABAの場合、答えは1です.

    • Solution

  • で分割されたファリンドロンの長さだけが、分割の回数を最小限に抑えることができる.
  • 文字列Sのサブ文字列が空かどうかを確認するには、O(N 3)を入力します.
    Memoizationを利用すると,時間的複雑度はO(N 2)である.キャッシュ[開始][終了]
    S[start:end-1]にパリンドロンが存在するか否かを配列で格納する.
  • あるsubstringはfallin dromであり、最後のインデックスがiの場合i+1から始まる
    パリンドロン串を探す過程を繰り返す.この過程を繰り返す
    数を数えて、最高価格を探します.
    • #include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cstring>

using namespace std;

int cache[2501][2501];
int dp[2501];
string str;
// 문자열의 start ~ (end - 1) Palindrome Check 
int isPalindrome(int start, int end){
	int& ret = cache[start][end];
	if(ret != -1) return ret;
	
	int len = (end - start) / 2;
	for(int i=0; i<len; i++){
		if(str[start + i] != str[end - 1 - i])
			return ret = 0;
	}
	return ret = 1;
}
// Palindrome의 집합으로 문자열을 표현하고 그 개수의 최솟값을 구한다.
int solve(int start){
	int len = str.length();
	int& ret = dp[start];
	if(ret != -1) return ret;
	if(start == len) return ret = 0;
	
	int mins = 10000;
	for(int i=start + 1; i<=len; i++)
		if(isPalindrome(start, i)){
			mins = min(mins, solve(i) + 1);
		}
	return ret = mins;
}

int main(){
	char s[2501];
	scanf("%s", s);
	str = s;
	
	memset(cache, -1, sizeof(cache));
	memset(dp, -1, sizeof(dp));
	int mins = solve(0);
	
	printf("%d \n", mins);
}

    Result


  • 上のコードでは、ソルバにコメントが書かれていないためタイムアウトします.
    • 2月15日学習日記#StringfyJson
    [白駿2438号]星を撮る-1|JavaScript