結果

問題 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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0