P3143 [USACO16OPEN] 다이아몬드 컬렉터 Diamond Collector

제목 설명Bessie the cow,always a fan of shiny objects,has taken up a hobby of mining diamonds in her spare time!She has collected diamonds () of varying sizes, and she wants to arrange some of them in a pair of display cases in the barn. Since Bessie wants the diamonds in each of the two cases to be relatively similar in size, she decides that she will not include two diamonds in the same case if their sizes differ by more than (two diamonds can be displayed together in the same case if their sizes differ by exactly ). Given , please help Bessie determine the maximum number of diamonds she can display in both cases together. 젖소 베스시는 반짝반짝 빛나는 것(Baling~Baling~)을 좋아하기 때문에 여가 시간에 다이아몬드를 캐는 것을 좋아한다!그녀는 현재 N개의 다른 크기의 다이아몬드(N<=50000)를 수집했고, 지금은 곡창의 두 진열대에 다이아몬드를 놓고 싶어 한다.Bessie는 이 진열대 위의 다이아몬드를 비슷한 크기로 유지하고 싶어 하기 때문에 두 개의 크기 차이가 K 이상인 다이아몬드를 한 진열대에 동시에 놓지 않는다(두 개의 다이아몬드의 크기 차이가 K라면 한 진열대에 동시에 놓을 수 있다).지금 K를 드리겠습니다. Bessie가 최대 몇 개의 다이아몬드를 이 두 진열대에 놓을 수 있는지 확인해 주세요.입력 출력 형식 입력 형식:
The first line of the input file contains and (). The next lines each contain an integer giving the size of one of the diamonds. All sizes will be positive and will not exceed .
출력 형식:
Output a single positive integer, telling the maximum number of diamonds that Bessie can showcase in total in both the cases.
입력 출력 예제 입력 예제 #1:7 3 10 5 1 12 9 5 14 출력 예제 #1:5
동적 기획: f[i]를 설정하면 i로 시작하는 최대 연장 길이를 표시하고 g[i]는 i로 시작하는 최대 연장 길이를 나타낸다.답은max{f[i+1]+g[i]}입니다.f, g를 구할 때 직접 폭력을 행사할 수 없기 때문에 최적화가 필요하다.

#include
#include
#include
using namespace std;
int n,k,ans,pos,cnt,a[50005],f[50005],g[50005];
int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)
        scanf("%d",a+i);
    sort(a+1,a+n+1);
    cnt=0,pos=n;
    for(int i=n;i>=1;i--)
    {  
        cnt++;
        int tmp=pos;
        for(int j=tmp;j>=1;j--)
        {
            tmp--;
            if(a[j]-a[i]<=k)
                break;
            else
                cnt--;
        }
        pos=tmp+1;
        f[i]=max(f[i+1],cnt);
    }
    cnt=0,pos=1;
    for(int i=1;i<=n;i++)
    {
        cnt++;
        int tmp=pos;
        for(int j=tmp;j<=n;j++)
        {
            tmp++;
            if(a[i]-a[j]<=k)
                break;
            else
                cnt--;
        }
        pos=tmp-1;
        g[i]=max(cnt,g[i-1]);
    }
    for(int i=1;i<=n;i++)
        ans=max(ans,f[i+1]+g[i]);
    printf("%d
",ans);
    return 0;
}