391B:Word Folding 욕심DP

B. Word Folding
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
You will receive 5 points for solving this problem.
Manao has invented a new operation on strings that is called folding. Each fold happens between a pair of consecutive letters and places the second part of the string above first part, running in the opposite direction and aligned to the position of the fold. Using this operation, Manao converts the string into a structure that has one more level than there were fold operations performed. See the following examples for clarity.
We will denote the positions of folds with '|' characters. For example, the word "ABRACADABRA"written as "AB|RACA|DAB|RA"indicates that it has been folded three times: first, between the leftmost pair of 'B' and 'R' letters; second, between 'A' and 'D'; and third, between the rightmost pair of 'B' and 'R' letters. Here are several examples of folded strings:

"ABCDEF|GHIJK" |  "A|BCDEFGHIJK" |  "AB|RACA|DAB|RA" |  "X|XXXXX|X|X|XXXXXX"
               |                 |                   |       XXXXXX
    KJIHG      |   KJIHGFEDCB    |      AR           |       X
   ABCDEF      |            A    |     DAB           |       X
               |                 |     ACAR          |       XXXXX
               |                 |       AB          |           X

One last example for "ABCD|EFGH|IJ|K":

 K
IJ
HGFE
ABCD

Manao noticed that each folded string can be viewed as several piles of letters. For instance, in the previous example, there are four piles, which can be read as "AHI", "BGJK", "CF", and "DE"from bottom to top. Manao wonders what is the highest pile of identical letters he can build using fold operations on a given word. Note that the pile should not contain gaps and should start at the bottom level. For example, in the rightmost of the four examples above, none of the piles would be considered valid since each of them has gaps, starts above the bottom level, or both.
Input
The input will consist of one line containing a single string of n characters with 1 ≤ n ≤ 1000 and no spaces. All characters of the string will be uppercase letters.
This problem doesn't have subproblems. You will get 5 points for the correct submission.
Output
Print a single integer — the size of the largest pile composed of identical characters that can be seen in a valid result of folding operations on the given string.
Sample test(s)
input

ABRACADABRA

output

3

input

ABBBCBDB

output

3

input

AB

output

1

Note
Consider the first example. Manao can create a pile of three 'A's using the folding "AB|RACAD|ABRA", which results in the following structure:

ABRA
DACAR
   AB

In the second example, Manao can create a pile of three 'B's using the following folding: "AB|BB|CBDB".

CBDB
BB
AB

Another way for Manao to create a pile of three 'B's with "ABBBCBDB"is the following folding: "AB|B|BCBDB".

 BCBDB
 B
AB

In the third example, there are no folds performed and the string is just written in one line.
제목: 문자열을 한 줄 주고 접어서 한 열에 같은 알파벳이 가장 많이 나타날 수 있도록 합니다.
사고방식: 접은 후의 길이나 너비를 최소화하려면 현재의 첫 번째 자모가 한 줄이거나 두 번째 자모가 한 줄이면 두 자모를 사이에 두고 또 한 줄이 된다. 그러면 이런 방법은 같은 열의 같은 자모의 수를 가장 많이 얻을 수 있다.
현재 첫 번째 알파벳이 첫 번째 줄이라면 가장 작은 길이를 접으면 가장 가까운 네 번째 알파벳이 첫 번째 알파벳과 같은 열을 만들 수 있기 때문이다. 예를 들어 첫 번째 견본 열에서

ABRA
DACAR
   AB

첫 번째 자모가 A이고 두 번째 자모가 A와 같은 열을 짓려면 아래에 가장 적게 표시된 것이 네 번째 자모, 즉 A이다.잠깐만, 잠깐만... 그래서 네 번째 자모의 숫자는 첫 번째 자모의 숫자 +1이고 DP는 내려가면 돼요.

#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <list>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
#define PI acos(-1.0)
#define mem(a,b) memset(a,b,sizeof(a))
#define sca(a) scanf("%d",&a)
#define pri(a) printf("%d
",a)
#define MM 10002
#define MN 1005
#define INF 168430090
using namespace std;
typedef long long ll;
int dp[MN],sum,l,i,j;
string a;
int main()
{
    cin>>a;
    l=a.size();
    for(i=0; i<l-1; i++)
        for(j=i+1; j<l; j+=2)
        {
            if(a[i]==a[j])
                dp[j]=dp[i]+1;
            sum=max(sum,dp[j]);
        }
    cout<<sum+1<<endl;
    return 0;
}