uva 417 - Word Index(디지털 dp)

6843 단어

제목 연결: uva 417 - Word Index


제목 대의: 제목의 요구에 따라 문자열의 번호를 매깁니다. 현재 문자열을 매깁니다. 번호가 얼마인지 물어보세요. 문자열은 반드시 점차적으로 증가해야 합니다. 그렇지 않으면 번호가 0이어야 합니다.
문제풀이 사고방식: 주어진 문자열보다 작고 증가하는 문자열이 몇 개인지 계산하는 것이다.dp[i][j]는 i번째 자리가 주어진 문자열보다 작고 증가하는 문자열을 만족시키는 j임을 나타낸다.dp[i][j]=∑k=0j−1dp[i−1][k]. 경계를 처리할 때마다 주의하고 마지막에 자신의 열을 붙여야 한다.또한 경계를 처리할 때 dp[i][0]가 1로 부여되어 이전 i개가 비어 있는 상황을 나타낸다.
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 10;
char str[N];
int dp[N][3*N];

int solve () {
    int len = strlen(str);

    if (len == 1)
        return str[0] - 'a' + 1;;

    for (int i = 1; i < len; i++)
        if (str[i] <= str[i-1])
            return 0;

    int pre = str[0] - 'a' + 2;
    memset(dp, 0, sizeof(dp));

    for (int i = 0; i + 'a' <= str[0]; i++)
        dp[1][i] = 1;

    for (int i = 1; i < len; i++) {

        for (int j = 0; j <= 26; j++) {
            for (int k = j+1; k <= 26; k++)
                dp[i+1][k] += dp[i][j];
        }

        for (int j = pre; j + 'a' <= str[i]; j++)
            dp[i+1][j]++;
        pre = str[i] - 'a' + 2;
        dp[i+1][0]++;
    }

    int ans = 1;
    for (int i = 1; i <= 26; i++)
        ans += dp[len][i];
    return ans;
}

int main () {
    while (scanf("%s", str) == 1) {
        printf("%d
", solve());
    }
    return 0;
}
Drawable의 aray를 xml 파일로 정의하여 보기 속성으로 읽기
HDU 4433 locker(SPFA+DP)

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

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