Hdu 2859-Phalanx(기초 dp)

3988 단어 dp
제목 링크:http://acm.hdu.edu.cn/showproblem.php?pid=2859
제목 대의:문자 방진 을 정 하고 가장 큰 자 방진 의 크기 를 구하 여 부 대각선 을 축 으로 완전히 대칭 시 킵 니 다.
분석:위 에서 아래로 O(n2)를 옮 겨 다 니 며 dp[i][j]를 보고 위치(i,j)위 와 오른쪽 의 총 일치 수 cnct(자신 포함 하지 않 음)를 봅 니 다.dp[i-1][j-1]보다 크 면 dp[i][j]를 dp[i-1][j-1]+1 로 업데이트 합 니 다.그렇지 않 으 면 dp[i][j]=cnct+1
실제로 처음에 생각 했 던 것 은 바로 이런 방법 이 었 다.그러나 추산 복잡 도 는 O(n3),1≤n≤1000,약 1e9 의 복잡 도 였 다.그래서 처음에는 예측 할 수 없 었 고 계속 생각 하지 않 았 다.나중에 문 제 를 보고 나 서 야 이 문 제 는 5s 의 문제 라 는 것 을 알 게 되 었 다.1e9 는 충분 하고 정말 좀 더 자세하게 해 야 한다.
코드:
#include
#include
#include
#include
#include
using namespace std;

typedef long long ll;

const int maxn = 1200;

int n;
char mat[maxn][maxn];
int dp[maxn][maxn];

int main()
{
    while (~scanf("%d",&n)&&n)
    {
        memset(dp,0,sizeof(dp));
        for (int i = 1 ; i <= n ; i ++)
        {
            scanf("%s",mat[i]+1);
        }
        int maxx = 1;
        for (int i = 1 ; i <=n ; ++i)
        {
            for (int j = 1 ; j <= n ; j ++)
            {
                if (i==1||j==n)
                {
                    dp[i][j] = 1;
                    continue;
                }
                int cnt = 0;
                for (int k = 1 ; k +j<=n && i - k>=1 ; k ++)
                {
                    if (mat[i-k][j]==mat[i][j+k])
                        cnt++;
                    else
                        break;
                }
                if (cnt>=dp[i-1][j+1])
                    dp[i][j] = dp[i-1][j+1]+1;
                else
                    dp[i][j] = cnt+1;
                maxx = max(dp[i][j],maxx);
            }
        }
        printf("%d
",maxx);
    }

    return 0;
}
(10)자바 도구 류 StringUtils 문자열 연결(join)상세 설명
연속 구역 의 최대 길이(간단 한 검색)

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage