結果
問題 | No.2204 Palindrome Splitting (No Rearrangement ver.) |
ユーザー |
![]() |
提出日時 | 2023-02-03 21:57:03 |
言語 | C (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 211 ms / 2,000 ms |
コード長 | 777 bytes |
コンパイル時間 | 441 ms |
コンパイル使用メモリ | 30,464 KB |
実行使用メモリ | 99,584 KB |
最終ジャッジ日時 | 2024-07-02 19:52:11 |
合計ジャッジ時間 | 6,178 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 33 |
ソースコード
#include <stdio.h>#include <string.h>int main () {char s[5001] = "";int res = 0;int ans[5001] = {};int dp[5000][5001] = {};int len = 0;res = scanf("%s", s);len = strlen(s);for (int i = 0; i < len; i++) {dp[i][i] = 1;dp[i][i+1] = 1;}for (int i = 1; i < len; i++) {for (int j = 0; j < len-i; j++) {if (s[j] == s[j+i] && dp[j+1][j+i] > 0) {dp[j][j+i+1] = 1;}}}ans[0] = len;for (int i = 0; i < len; i++) {for (int j = i+1; j <= len; j++) {if (dp[i][j] > 0) {int min = ans[i];if (min > j-i) {min = j-i;}if (min > ans[j]) {ans[j] = min;}}}}printf("%d\n", ans[len]);return 0;}