두 개의 비교적 좋은 dp 문제 codeofrces 1196 D2 1256 E

요 며칠 동안 두 개의 비교적 좋은 dp문제를 풀었는데 많은 dp문제가 이렇다고 느꼈다. 바로 O(n*n)의 dp를 생각하기 쉽다. 그러나 O(n*n)는 시간을 초과할 수 있기 때문에 어떻게 최적화해야 할지 생각했다. 때로는 O(n*logn)로 낮출 수 있고 때로는 사고문제도 있다. 생각만 하면 O(n)의 dp로 낮출 수 있다. 가장 일반적인 dp이다.느낌이 모두 비교적 유사하니 여기서 총괄해 보자.
codeforces 1196 D2
제목: n 길이의 문자열 a와 정수 k를 드리겠습니다. 최소한 몇 글자를 바꾸면 이 문자열에 k 길이의 하위 문자열이 존재합니다. 문자열은'RGBRGBRGB...'입니다.라는 문자열을 남겼다.k<=n<=2e5
우선 O(n*n)의 dp는 매우 그리워요.
mp['R']=1, mp['G']=2, mp['B']=3.
dp[i][j][k]는 전 i자 중 길이가 k인 하위 문자열을 구성하고 (이 하위 문자열은 i로 끝난다. 즉, a[i-k+1]에서 a[i]까지이며 mp[a[i]=k)가 바꿔야 할 최소 횟수를 나타낸다.
상태 이동 방정식: dp[i][j][k]=min(dp[i][j][k], dp[i-1][j-1][k-1]+(mp[a[i]]===k?0:1) 만약 k가 1이면 k-1은 3으로 바뀐다.
그러나 이것은 분명히 T(D1의 데이터 범위가 작아서 이렇게 AC할 수 있다)
 
그리고 우리가 어떻게 최적화하려고 하는지 우리는 길이가 1에서 k까지의 자열을 기록하지 않을 수 있다. 우리는 길이가 k인 것만 기록하면 된다. 이렇게 하면 상태 이동도 할 수 있다.
dp[i][j]는 전 i자 중 길이가 k인 하위 문자열을 구성하고 (이 하위 문자열은 i로 끝난다. 즉, a[i-k+1]에서 a[i]까지이며 mp[a[i]=j)가 변경해야 할 최소 횟수를 나타낸다.상태 이동 방정식: dp[i][j]=min(dp[i][j], dp[i-1][j-1]+(mp[a[i]]]==k?0:1)-f) 만약 j등이 1이면 j-1은 3으로 바뀐다.
그 중에서 f의 값은 0 또는 1이고 mp[a[i-k]]=j-(k%3)일 때 f=0이며 그렇지 않으면 f는 1이다.
상세 코드:

#include
#define mem(a,b) memset((a),b,sizeof(a))
#define de cout< mp;
void init()
{
    for(int p=1;p<=3;p++)
    {
        int num=0;
        int pp=p;
        for(int i=kk;i>=1;i--)
        {
            if(mp[a[i]]!=pp)
                num++;
            pp--;
            if(pp<1) pp=3;
        }
        dp[kk][p]=num;
    }
}
int main()
{
    mp['R']=1;
    mp['G']=2;
    mp['B']=3;
    int T;scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&kk);
        scanf("%s",a+1);
        if(n==1||kk==1)    {printf("0
");continue;}
        for(int i=0;i<=n;i++)
            for(int j=1;j<=3;j++)
                dp[i][j]=inf;
        init();
        int f,K;
        for(int i=kk+1;i<=n;i++)
        {
            for(int j=1;j<=3;j++)
            {
                f=0;
                K=kk%3;
                K=j-K;
                if(K<1)
                    K+=3;
                if(mp[a[i-kk]]!=K)
                    f=1;
                if(mp[a[i]]==j)
                {
                    if(j==1)
                        dp[i][j]=min(dp[i][j],dp[i-1][3]-f);
                    else
                        dp[i][j]=min(dp[i][j],dp[i-1][j-1]-f);
                }
                else
                {
                    if(j==1)
                        dp[i][j]=min(dp[i][j],dp[i-1][3]+1-f);
                    else
                        dp[i][j]=min(dp[i][j],dp[i-1][j-1]+1-f);
                }
            }
        }
        int ans=inf;
        for(int i=kk;i<=n;i++)
            for(int j=1;j<=3;j++)
                ans=min(ans,dp[i][j]);
        printf("%d
",ans);
    }
    return 0;
}

 codeforces 1256 E
제목: n개의 수를 주고 이 n개의 수를 그룹으로 나누라고 한다. (몇 개의 그룹으로 나누어도 되지만 각 그룹의 인원은 반드시 3보다 많아야 한다) 각 그룹의 그룹 값은 그룹 안의 최대 값으로 최소 값의 차이를 줄이고 어떻게 그룹을 나누어야 이 그룹의 그룹 값과 최소 값을 줄일 수 있는지 묻는다.n<=2e5
우선 이 n개의 수를 순서대로 배열해라. 왜냐하면 틀림없이 값이 비슷한 수를 함께 나누기를 원하기 때문이다
우선, O(n*n)의 dp는 여전히 매우 그리워한다.
dp[i]는 이전 i에 대한 개인 그룹을 표시하고 그룹 값의 크기와 최소는 dp[i]이다.dp[i]=min(dp[i],dp[j]+a[i]-a[i-j+1])        3<=i-j  &&  j>=3
하지만 우리는 j를 이렇게 여러 번 순환시킬 필요가 없다.
만약에 우리가 6명을 한 조로 나누면 반드시 가장 좋은 것은 아니다. 왜냐하면 우리는 이 6명을 셋, 셋의 두 조로 나눌 수 있기 때문이다. 이렇게 하면 6명의 한 조보다 나쁘지 않기 때문에 한 조의 인원은 단지 세 가지 상황: 셋, 넷, 다섯이다.
dp[i]는 이전 i에 대한 개인 그룹을 표시하고 그룹 값의 크기와 최소는 dp[i]이다.dp[i]=min(dp[i],dp[i-3]+a[i]-a[i-2],dp[i-4]+a[i]-a[i-3],dp[i-5]+a[i]-a[i-4])

#include
#define mem(a,b) memset((a),b,sizeof(a))
#define de cout<=8)
            dp[i]=min(min(dp[i-3]+a[i].v-a[i-2].v,dp[i-4]+a[i].v-a[i-3].v),dp[i-5]+a[i].v-a[i-4].v);
        else if(i>=7)
            dp[i]=min(dp[i-3]+a[i].v-a[i-2].v,dp[i-4]+a[i].v-a[i-3].v);
        else
            dp[i]=dp[i-3]+a[i].v-a[i-2].v;
    }
    printf("%I64d ",dp[n]);
    ans=0;
    for(int i=n;i>=3;i--)
    {
        if(i>=5&&dp[i]==dp[i-5]+a[i].v-a[i-4].v)
            a[i].idd=++ans,a[i-1].idd=ans,a[i-2].idd=ans,a[i-3].idd=ans,a[i-4].idd=ans,i-=4;
        else if(i>=4&&dp[i]==dp[i-4]+a[i].v-a[i-3].v)
            a[i].idd=++ans,a[i-1].idd=ans,a[i-2].idd=ans,a[i-3].idd=ans,i-=3;
        else if(i>=3&&dp[i]==dp[i-3]+a[i].v-a[i-2].v)
            a[i].idd=++ans,a[i-1].idd=ans,a[i-2].idd=ans,i-=2;
    }
    printf("%d
",ans);
    sort(a+1,a+n+1,cmp2);
    printf("%d",a[1].idd);
    for(int i=2;i<=n;i++)
        printf(" %d",a[i].idd);
    puts("");
    return 0;
}