結果

問題 No.2204 Palindrome Splitting (No Rearrangement ver.)
コンテスト
ユーザー tokitsukaze
提出日時 2025-02-17 01:12:35
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 217 ms / 2,000 ms
コード長 673 bytes
コンパイル時間 1,503 ms
コンパイル使用メモリ 159,352 KB
実行使用メモリ 101,304 KB
最終ジャッジ日時 2025-02-17 01:12:44
合計ジャッジ時間 7,723 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 33
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:12:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   12 |         scanf("%s",s+1);
      |         ~~~~~^~~~~~~~~~

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
const int MAX=5000+10;
char s[MAX];
int dp[MAX],g[MAX][MAX];
int main()
{
	int n,i,j,len,l,r;
	scanf("%s",s+1);
	n=strlen(s+1);
	for(i=1;i<=n;i++) g[i][i]=1;
	for(i=1;i<n;i++)
	{
		if(s[i]==s[i+1]) g[i][i+1]=1;
	}
	for(len=3;len<=n;len++)
	{
		for(l=1;l+len-1<=n;l++)
		{
			r=l+len-1;
			if(s[l]==s[r]) g[l][r]=g[l+1][r-1];
			else g[l][r]=0;
		}
	}
	dp[0]=INF;
	for(i=1;i<=n;i++)
	{
		dp[i]=1;
		for(j=1;j<=i;j++)
		{
			if(g[j][i]==0) continue;
//			cout<<j<<" "<<i<<endl;
			dp[i]=max(dp[i],min(dp[j-1],i-j+1));
		}
	}
	printf("%d\n",dp[n]);
	return 0;
}
0