noip2015 꼬치(소감)

오늘 드디어 리그 향상팀에서 동적 기획(Dynamic 프로그램)을 만났습니다.다행히도 4인조에서 수석을 차지했다. (이형의 강점은 AVL 나무, 붉은색, 검은색 나무, 라인 트리, 스트레칭 나무, 점프 시계, 단조로운 대열, 최근에 공공 조상, 배증, 접두사 자동기, ac 자동기 등 고급 응용에 있어 간단한 동태 계획이 약하다. [하지만 나무 모양 dp, 형상 압력 dp가 매우 강해서 그를 알아보지 못한다] 오늘 그를 가까스로 물리치고 이형의 블로그 주소를 공유한다.http://blog.csdn.net/lycheng1215) 동태적인 기획, 첫 번째 단계, 문제를 해체한다.단순한 귀속에 주의하면 종종 하위 문제가 중복 계산될 수 있다. 동적 기획 방법으로 하위 문제의 해답을 구하면 보존되기 때문에 모든 하위 문제는 한 번만 해답해야 한다.자문제는 항상 원문제와 형식이 비슷하지만, 때로는 완전히 같기도 하다. 단지 규모가 원래의 n에서 n-1로 바뀌었거나 원래의 n에서×n이 되다×(m-1)...등등.이 문제는 순서대로 하위 문자열 A의 n-1 위치를 찾는 것이다. 몇 가지 방안이 이 찾은 새 문자열을 문자열 B와 같게 할 수 있는가.B에 대해서도 하위 문제가 있다. 바로 B가 j-1 위치에 도착했을 때 i에서 얼마나 추출할 수 있는지이다.하위 문제를 찾았다는 것은 전체 문제를 점차적으로 분해하는 방법을 찾았다는 것을 의미한다.밑바닥에서 규모가 가장 작은 하위 문제가 한눈에 알아볼 때까지 분해해 보자.가장 작은 문제는 1위치까지 몇 가지 방안이 있느냐는 것이다. 분명히 길이가 B열보다 작으면 여기는 0이다.동적 기획으로 문제를 풀 때 하위 문제와 관련된 각 변수의 값을 추출하여 하나의'상태'라고 부른다.하나의'상태'는 하나 이상의 하위 문제에 대응한다. 이른바 어떤'상태'아래의'값'은 바로 이'상태'에 대응하는 하위 문제의 해답이다.이 문제의 상태는 바로 A열의 i 위치와 앞의 모든 위치에서 k번을 취하면 B열의 앞j 부분과 같은 새 열이 몇 개 있을 수 있는지이다.s[i][j][k]라고 부른다.'상태'가 무엇인지, 그리고 이'상태'아래의'값'을 정의한 후에 서로 다른 상태 사이를 어떻게 이동하는지, 즉 어떻게 하나 이상의'값'에서 이미 알고 있는'상태'에서 다른'상태'의'값'을 구하는지 찾아내야 한다.상태의 이동은 추이 공식으로 표시할 수 있으며 이 추이 공식은'상태 이동 방정식'이라고 할 수 있다.그러면 어떻게 상태 이동 방정식으로 이 n의 문제를 1로 옮깁니까?이게 핵심이야.생각해보면 s[i][j][k]는 무엇으로 분해될 수 있습니까?만약에 A열의 i위와 B열 j위가 대응한다면 s[i][j][k]=1.i 위치를 선택하지 않은 문자의 추출 동일량 +2.i 위치의 문자의 추출 동일량을 선택했습니다.1. s[i-1][j][k]가 아닐까?그러면어떡하지?내가 선택한 것은 보조적인 f[i][j][k]를 열어 2.질문이 또 왔습니다. 어떻게 f[i][j][k]를 유지보수합니까?생각하고 다시 생각하고 계속 분해해서 현재 i위치와 j위치의 상등이라는 조건을 분석해 보면 만족한다. 그러면 i-1위치와 j-1이 제시한 상등자열이 여러 개 있는데 여기에 여러 개가 있는 거 아니야?바로 전제에 해당하는 자열이다. 가설은 s이고 지금 제기된 자열은 s+A[i]이다. 개수는 같지 않니?정답은 아니다.대신은 이렇게 말했다. 만약에 A[i-1]=B[j-1]A[i-3-1]=B[j-3-1]이면 AA를 꿰는 i-1i-3의 위치는 i-2i-3의 위치와 한 조를 합성할 수 있고 이때 조의 수는 변하지 않는다.i-2i-3의 위치와 한 조를 합성하지 않고 한 조를 만들 수도 있는데, 이때 조수는 +1이다.oh,no.

#include 
#include 
#include 
using namespace std;
const int maxn = 505, maxm = 55, mod = 1000000007;
int m, n, k;
char s1[maxn], s2[maxm];
int f[maxn][maxm][maxm], s[maxn][maxm][maxm];
void dp() {
    s[0][0][0] = 1;
    for(int i = 1; i <= n; ++i) {
        s[i][0][0] = 1; 
        for(int j = 1; j <= m; ++j)
            if(s1[i-1] == s2[j-1]) {
                for(int t = 1; t <= min(k, j); ++t) {
                    f[i][j][t]=(s[i-1][j-1][t-1] + f[i-1][j-1][t]) % mod,
                    s[i][j][t]=(s[i-1][j][t] + f[i][j][t]) % mod;
                }
            }else for (int t=1;t<=min(k, j); ++t) s[i][j][t] = s[i-1][j][t]; 
    }
    printf("%d
", s[n][m][k]);
}
int main() {
    freopen("substring.in","r",stdin);
    freopen("substring.out","w",stdout);
    scanf("%d%d%d%s%s", &n, &m, &k, s1, s2);
    dp();
    return 0;
}

그리고 7시를 넘을 수밖에 없어요. 범위가 부족해요.여기서 새로운 알고리즘을 배워야 한다.스크롤 배열.스크롤 그룹의 역할은 공간을 최적화하는 데 있으며 주로 점차적으로 추진하거나 동적 기획에 응용된다(예를 들어 01배낭 문제).DP 문제는 밑에서 위로 확장되는 과정이기 때문에 우리는 항상 연속적인 풀이를 필요로 하고 앞의 풀이는 버릴 수 있다.그래서 스크롤 그룹으로 최적화하는 것이 효과적이다.스크롤 그룹을 이용하면 N이 큰 상황에서 압축 저장 작용을 할 수 있다.원리는 매우 간단하다. 이형은 간단명료하고 이해하기 쉽다고 말했는데, 나조차도 20minute만 써서 이해했으니, 모두들 스스로 뒤져 보아라.