HDU 4055 Number String

1671 단어
제목:
문자열 s, s[i] ='D'는 배열 중 a[i] > a[i+1], s[i] ='I'는 배열 중 a[i] 예를 들어 배열 {3, 1, 2, 7, 4, 6, 5}은 문자열 DIIDID로 표시됩니다.
문제 해결 방법:
교묘한 DP 방법은 dp[i][j]는 앞의 i개가 문자열 조건을 충족시키는 결말이 j인 i의 배열을 나타낸다. 주의는 i의 배열이고 앞의 수는 i보다 크지 않다.그것은 또 어떻게 아래로 밀어내는가?
만약 s[i-1]가'I'라면 dp[i][j]=dp[i-1][j-1]+dp[i-1][j-2]+..+dp[i-1][1]
만약 s[i-1]가'D'라면 dp[i][j]=dp[i-1][j]+dp[i-1][j+1]+...+dp[i-1][i]는 현재 위치를 j로 해야 하기 때문에 앞에 j가 나타나면 앞에 있는 모든 것이 j보다 큰 수를 +1로 하면 새로운 배열을 구성할 수 있다.예컨대
{1,3,5,2,4}, 6위에 3을 삽입하고 >=3의 수를 모두 +1하여 새로운 배열 {1,4,6,2,5,3}을 구성한다.그리고 코드는 접두사와sum[i][j]를 처리하고 dp[i][j]를 사용하지 않습니다.그래도 교묘한 것 같아, 좋은 문제야!
/* **********************************************
Author      : JayYe
Created Time: 2013/10/6 23:22:51
File Name   : Orz.cpp
*********************************************** */

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
typedef __int64 ll;

const int maxn = 1000 + 5;
const int mod = 1000000007;

ll sum[maxn][maxn];
char s[maxn];

int main() {
    while(scanf("%s", s) != -1) {
        int len = strlen(s);
        sum[0][1] = 1;
        for(int i = 1;i <= len; i++) {
            for(int j = 1;j <= i+1; j++) {
                sum[i][j] = sum[i][j-1];
                if(s[i-1] != 'D')
                    sum[i][j] += sum[i-1][j-1];
                if(s[i-1] != 'I')
                    sum[i][j] += sum[i-1][i] - sum[i-1][j-1] + mod;
                sum[i][j] %= mod;
            }
        }
        printf("%I64d
", sum[len][len+1]);
    }
    return 0;
}
Rails 서버 강제 정지법
Axios를 사용한 Alexa API 호출

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

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