[NOIP2010] 거북이 바둑(DP)

3664 단어 dp수돗물
전송문 사고방식: 고전적인 DP문제, 내가 물을 한 번 흘린 다음에 데이터 범위를 보면 이것이 다차원 DP라는 것을 알 수 있다. 우리는 F(i, j, k, l, m)를 설정하여 i걸음을 걸었다는 것을 나타낼 수 있다. 첫 번째 카드는 j장, 두 번째 카드는 k장, 세 번째 카드는 l장, 네 번째 카드는 m장 이후의 최대 점수를 사용했다.그러나 우리는 이렇게 옮기면 메모리가 켜지지 않을 뿐만 아니라 옮길 때 시간이 초과된다는 것을 발견했다. 어떡하지? 우리는 이 다섯 개의 수가 독립된 것이 아니라 4에서 5를 구할 수 있다는 것을 발견했다. 그래서 우리는 1차원을 마음대로 절약하면 4차원 공간이 되고 켜질 수 있다는 것을 발견했다.
코드:
#include<cstdio>
inline int max(int a,int b){return a>b?a:b;}
int n, m;
int a[355], card[5];
int f[41][41][41][41];
int main()
{
    int i,k,j,l;
    scanf("%d%d",&n,&m);
    for(i = 1; i <= n; i ++) scanf("%d",&a[i]);
    for(i = 1; i <= m; i ++)
    {
        scanf("%d",&j);
        card[j]++;
    }
    for(i=0; i<=card[1]; i ++)
    for(j=0; j<=card[2]; j ++)
    for(k=0; k<=card[3]; k ++)
    for(l=0; l<=card[4]; l ++)
    {
        int a1 = i==0?0:f[i-1][j][k][l];
        int a2 = j==0?0:f[i][j-1][k][l];
        int a3 = k==0?0:f[i][j][k-1][l];
        int a4 = l==0?0:f[i][j][k][l-1];
        int t = max(max(a1,a2),max(a3,a4));
        f[i][j][k][l] = t+a[i+2*j+3*k+4*l+1];
    }
    printf("%d",f[card[1]][card[2]][card[3]][card[4]]);
}
docker registry fronted 설치
Docker의 PhantoomJS로 캡처하기

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

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