dp(첫 번째 시도)

제목: 클릭하여 링크 열기
코드:

#include
#include
#include
#include 
#include
#include
#include
#include
#include
#include
using namespace std;

typedef long long LL;
const int INF = (1<<30)-1;
const int mod=1000000007;
const int maxn=1000005;

int a[maxn],f[maxn];
int main()
{
    int T;
    scanf("%d",&T);
    int kase=0;
    while(T--)
    {
        int n;
        scanf("%d",&n);
        for(int i=1; i<=n; i++)
        {
            scanf("%d",&a[i]);
            a[i]=a[i]-i;
        }

        int len=1;
        f[1]=a[1];
        for(int i=2; i<=n; i++)
        {
            if(a[i]>=f[len]) f[++len]=a[i];//              ，     
            else
            {
                int pos=upper_bound(f+1,f+len+1,a[i])-f;//upper_bound           key      
                f[pos]=a[i];
            }
        }
        printf("Case #%d:
",++kase);
        printf("%d
",n-len);
    }
    return 0;
}

사실 이 dp는 내가 특별히 잘하지는 못하지만 이 코드는 내가 좀 알아봤지만 특별히 아는 것은 아니다. 단지 이것이 옳다고 추측할 수 있을 뿐이다. 어쨌든 느낌이 비교적 강하다. 이 안에 또 하나의 함수가 있다. 바로lowerbound는 이 값보다 큰 첫 번째 위치를 되돌려줍니다. upperbound는 이 값보다 큰 첫 번째 값을 되돌려줍니다
값의 위치는 사실 특별히 이해하지 못한다. 어차피 다른 사람의 코드를 봤기 때문에 전체적인 사고방식도 특별히 명확하지 않다.

dp(첫 번째 시도)

좋은 웹페이지 즐겨찾기