| 낙 곡 | 동적 계획 | P1108 저가 구 매

1116 단어
http://www.luogu.org/problem/show?pid=1108
첫 번 째 질문 은 최 장 하강 서브 시퀀스 이 고 두 번 째 줄 은 하강 서브 시퀀스 의 개수 (같 을 수 없 음) 이다.
현재 i 는 앞의 방안 수 를 더 하고 같은 숫자 에 마지막 하나만 더 합 니 다.
ok [j] 로 가격 이 j 인 주식 이 이미 추가 되 었 음 을 표시 하고 역 추 는 위의 조건 을 보장 할 수 있다.
#include
#include
#include
#include
#define ms(i,j) memset(i, j, sizeof(i));
using namespace std;
int a[5005];
int b[5005];
int f[5005];
bool ok[50005];
int main()
{
    int n;
    scanf("%d", &n);
    for (int i=1;i<=n;i++) scanf("%d", &a[i]);
    b[1] = 1;
    f[1] = 1;
    for (int i=2;i<=n+1;i++)
    {
        int max = 0;
        f[i] = 1;
        for (int j=i-1;j>0;j--)
        {
            if (a[i]max)
{
max = b[j];
ms(ok, true);
ok[a[j]] = false;
f[i] = f[j];
} 
else
{
if (b[j]==max&&ok[a[j]])
{
ok[a[j]] = false;
f[i] += f[j];
}
}
}
b[i] = max+1;
} 
printf("%d %d", b[n+1]-1, f[n+1]);
return 0;
}

다음으로 전송:https://www.cnblogs.com/flyinthesky1/p/6384289.html

좋은 웹페이지 즐겨찾기