동적 계획 - 하위 시퀀스 수

3696 단어 dp동적 기획시퀀스 개수
하위 시퀀스 개수
제목 상세 정보: 하위 서열의 정의: 하나의 서열에 대한 a=a[1], a[2],......a[n], 비공식 서열 a'=a[p1], a[p2]......a[pm]는 a의 하위 서열로 그 중 1<=p1예를 들어 4,14,2,3과 14,1,2,3은 모두 4,13,14,1,2,3의 서열이다.서열 a를 제시하는 데 있어서 일부 서열은 같을 수 있습니다. 여기는 1개만 하고 a의 서로 다른 서열의 수량을 출력해야 합니다.
입력: 길이가 n인 수조 1<=n<=100, 수조 원소 0<=a[i]<=110
출력: 하위 서열의 개수가 1000000007에 대한 나머지 결과를 얻습니다. (답이 비교적 크기 때문에 Mod 1000000007의 결과를 출력하면 됩니다.)
함수 헤더: C/C++: int run (cons int *a, int n);java   public static int run(int [] a); 
이 문제도 나를 오랫동안 괴롭혔지만 좋은 방법을 찾지 못했다. 이 문제는 동적 기획으로 풀 수 있을 것이다. 그래서 나도 동적 기획의 사상을 배우고 연습 문제를 찾아냈다. 그러나 이 상태의 전환 방정식은 나를 견디기 어렵다. 원래 수학의 기초가 보통이어서 더욱 난이도가 높아졌다.비록 내가 최종적으로 이 문제를 해결했지만 그것은 대신의 지시를 받은 상황에서 만들어진 것이다. 나는 여기서 단지 문제를 풀고 쓴 김에 결점을 보완하고 자신의 이해가 정확한지 보려고 한다. 사실은 하고 싶은 것과 하는 것은 별개의 일이니 여러분도 바로잡아 주십시오.
문제 풀이:
서열의 전 k개수의 서열 개수가 d(k)라고 가정하면 전 k-1 서열의 개수는 d(k-1) 서열이다. k-1에서 k로의 변화는 어떠한가?
1. 수조 a[N]의 k번째 수가 a[k]라고 가정하고 a[k]가 앞의 k-1개수와 같지 않으면 d(k)=d(k-1)+[d(k-1)+1]=2d(k-1)+1이 있는데 왜 그럴까요?이렇게 생각할 수 있다. 앞의 k-1항의 서열 개수는 d(k-1)이다. 그 앞의 k개수는 앞의 k-1항의 토대 위에서 하나의 수 a[k](a[k]와 앞의 k-1개의 수가 임의로 같다). 그러면 원래의 조합에 a[k]를 더하면 d(k-1)개가 있고 또 하나의 a[k]가 스스로 서열을 구성하기 때문에 1을 추가해야 한다.
2. a[k]가 앞의 k-1개수 중 하나와 같다고 가정하면 앞의 k-1 하위 서열 개수 d(k-1)를 더한다. 그러나 앞에 a[k]와 같은 수가 있기 때문에 중복된 부분을 빼고 중복된 부분을 어떻게 찾을까. k에서 가장 가까운 a[k]와 같은 수가 첫 번째 a[t]=a[k], 즉 서열(a[1], a[2],a[2],...,a[k-1],a[k],a],a[k]],a[k]]],a[k]]]],a[k][k]][k]]]].우리는 이미 서열(a[1], a[2],......, a[t])의 서열 개수가 d(t)라는 것을 알고 있다. 그러면 d(t-1)는 중복된 부분이다. 여기는 스스로 생각을 잘 해야 하고 알고리즘의 관건적인 부분이다. 여기서 내가 설명하고자 하는 것은 왜 k에서 가장 가까운 t를 찾아서 a[t]=a[k]를 만들 수 있느냐는 것이다.설명은 다음과 같다. 우리는 1-n에서 수조를 두루 훑어보았고 d(i)를 계산하는 i는 1에서 n까지 순서대로 계산했다. 그러면 a[k]=a[t]를 처음 만났을 때 조건을 충족시켰다. 그리고 단 하나의 t만 a[t]=a[k]를 만들었다. 예를 들어 서열(1, 2, 3, 2, 4, 2)을 각각 d(1), d(2), d(3), d(4), d(5), d(6)를 계산했다.우리는 d(4)를 계산할 때 a[4]=a[2](하표가 1부터 시작한다고 가정)를 발견했기 때문에 d(4)=2*d(3)-d(2-1)=2d(3)-d(1)를 발견했다.d(6)를 계산할 때도 a[6]=a[4]=a[2]가 있지만 우리 앞에 a[2]가 중복된 부분을 줄였기 때문에 더 이상 줄일 필요가 없다. d(6)=2*d(5)-d(4-1)=2d(5)-d(3).
과정이 번거로우니 결론을 총괄해 보겠습니다.
상태 전환 방정식은 다음과 같습니다.
　　　　d(k) = 2 * d(k - 1) + 1;   a[k] != a[i],i = 1,2,3……k - 1;
　　　  d(k) = 2 * d(k - 1) - d(t - 1); k에서 검색하면 k에서 가장 가까운 t가 존재하여 a[t]=a[k].
상태 전이 방정식을 분석하면 나머지는 기본적으로 식은 죽 먹기입니다. 코드는 다음과 같습니다.
  
/*
           ：       ：      a=a[1],a[2],......a[n]，
         a'=a[p1],a[p2]......a[pm] a      ，  1<=p1<p2<.....<pm<=n。 
      ：4,14,2,3 14,1,2,3  4,13,14,1,2,3    。       a，           ，
         1 ，    a         。   ：    n   1<=n<=100,    0<=a[i]<=110
      ：        1000000007      （       ，  Mod 1000000007     ）。
        ： C/C++:   int run(cons int *a,int n); java   public static int run(int [] a);
*/
#include <stdio.h>
#include <stdlib.h>
#define M 1000000007
int run(const int *a,int n)
{
    long long SubArray[120] = {0};
    int LastIndex[120] = {0};
    int iter = 0;
    for(iter = 1; iter <= n; iter++)
    {
        switch(LastIndex[a[iter - 1]])
        {
        case 0:
            {
                SubArray[iter] = (2 * SubArray[iter - 1] + 1) % M;
                break;
            }
        default:
            {
                SubArray[iter] = (2 * SubArray[iter - 1] - SubArray[LastIndex[a[iter - 1]] - 1] + M) % M;
                break;
            }
        }
        LastIndex[a[iter - 1]] = iter;
    }
    return SubArray[n] % M;
}
int main(void)
{
    //int a[5] = {1, 2, 2, 3 ,3};
    int a[4] = {1, 2, 3 , 2};
    printf("the result is %d
", run(a, 4));
    return 0;
}

참고: 이 블로그는 블로그 텃밭의 블로그와 동일한 블로그 소유자입니다.http://www.cnblogs.com/bestDavid/
 
React with Hooks를 위한 빠르고 쉬운 로드 스피너 튜토리얼
깊이 이해 cv:: Mat

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

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