hdu 5064 Find Sequence(단순화 최적화 DP)

hdu 5064 Find Sequence

처음에 순서를 먼저 정한 다음에 둘씩 줄여서 LIS를 찾아내서 결과를 얻으려고 생각했는데, 분명히 주도면밀하게 고려하지 않았다
문제 풀이에 따라 이 문제는 단조로운 DP를 사용해야 한다.DP[i][j]는 시퀀스가 다음과 같이 i와 j로 끝나고, 변환 방정식은
DP[i][j] = max(DP[k][i] + 1) { k<=i && num[j] - num[i] >= num[i] - num[k] }
그러나 직접 구해 시간의 복잡도는 O(n^3)이다.이 상태 방정식은 특수한 성질을 가지고 있다. 즉,
k가 {k<=i & &num[j]-num[i]>=num[i]-num[k]}를 만족시키면 k는 j+1의 상황에서도 만족한다.그래서 j+1을 계산할 때 k는 바로 이전 상태에서 계속 진행할 수 있다.

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
#ifdef __GNUC__
typedef long long LL;
inline void opt64(LL a)
{
    printf("%lld", a);
}
#else
typedef __int64 LL;
inline void opt64(LL a)
{
    printf("%I64d", a);
}
#endif
const int MAXN = (1<<22)+5;
const int MAXM = 2050;
const double eps = 1e-10;
const double PI = acos(-1.0);
inline int cmp(const double x, const double y)
{
    return ((x-y)>eps) - ((x-y)eps) - ((x)=0 && mq[j]-mq[i]>=mq[i]-mq[k]; --k)
            {
                ans = max(ans, dp[k][i]);
            }
            dp[i][j] = ans+1;
            res = max(res, ans+1);
        }
    }
    return res;
}
int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif
    int t;
    scanf("%d", &t);
    while (t--)
    {
        scanf("%d%d", &n, &m);
        for (int i = 0; i< n; ++i)
            scanf("%d", mp+i);
        printf("%d
", solve());
    }
    return 0;
}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

[BOJ]11048(python)

python 풀이 DP를 이용해 풀이 보통 이런 문제는 dfs나 bfs로 풀이하는 것이여서 고민을 했는데 이 문구 덕분에 DP 를 이용해 풀이할 수 있었다 뒤로 돌아가는 등의 경우를 고려하지 않아도 되기 때문이다 코...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

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