김명의 예산 방안[동태 기획]

6205 단어 NOIP동적 기획
의존 01 가방 질문
dp를 할 때 차원이 명확해야 한다. 먼저 설계된 상태를 고려한 다음에 이전을 고려해야 한다. 이전은 어떤 결정이 있는지 고려해야 한다. 결정을 고려할 때 반드시 신중해야 하며 빠뜨려서는 안 된다.마지막으로 경계를 고려한다. 만약에 경계를 처리할 수 없다면 첫 번째 단계의 답안을 먼저 뛰어나올 수 있다. 상태의 디자인에 대해 답안을 어떻게 디자인했는지 생각해 볼 수 있다.
편리하게 볼 때, 우리는 상태를 메인 부품에만 정의한다. (입력에 대해 특수 처리를 한다) 각 메인 부품은 0, 1, 2개의 첨부 파일을 구매할 때마다 다섯 가지 선택이 있다.안 사요.주문만 구입바이어와 1호 부속품 4.바이어와 2번 부속품 5.구매자 및 모든 액세서리
[i][0]는 주부품의 가치와 비용을 나타낸다[i][1]는 1호 부속품의 가치와 비용을 나타낸다[i][2]는 2호 부속품의 가치와 비용을 나타낸다. 한 물품에 부속품이 없을 때 [i][1]과 [i][2]는 모두 0이다.
상태 전이 방정식(단지 하나의 사고방식 방정식일 뿐, 완전하지 않다! 기대치를 곱한 것이 적혀 있지 않으니, 구체적인 방정식은 코드를 아래로 보십시오) f(i, j) = max(f(i-1, j)),//f(i-1, j),j-c[i][0])+v[i] + v[i] [0]][0]]], 구체적인 방정식은 코드를 아래로 보십시오) f(i, j) = max(f(i-1, j-c[i] [0]]- c[i][i] + v[i] + v[i] + v[i] [1] [i] [1] [1] [[[i] [1] [[i] [[[i]] [[[[i] [[i] [1]]]]]]]][[[[[[[[[[[] + v[i][2],//메인 부품과 2번 부속품 f(i-1, j-c[i][0]-c[i][1]-c[i][2]) + v[i][0]+ v[i][1]+v[i][2],//메인 부품과 모든 부속품)
#include 
#include 
int f[72][32010],m,n,c[72][3],v[62][3];
int main() {
    scanf("%d%d",&n, &m);
    for(int i=1; i<=m; i++) {
        int w, p, q;
        scanf("%d %d %d",&w,&p,&q);
        if(q == 0) {
            c[i][0] = w;
            v[i][0] = p;
            continue;

        }
        if(!v[q][1]) { //              
            c[q][1] = w;
            v[q][1] = p;
        }
        else { //            
            c[q][2] = w;
            v[q][2] = p;
        }
    }
    for(int i=1; i<=m; i++) {

        for(int j=10; j<=n; j+=10){

            if(j-c[i][0]>= 0) {

                f[i][j] = std::max(f[i-1][j],f[i-1][j-c[i][0]] + v[i][0]*c[i][0]);

            if(j - c[i][0] - c[i][1] >= 0)

                f[i][j] = std::max(f[i][j],f[i-1][j-c[i][0]-c[i][1]] + v[i][1]*c[i][1] + v[i][0]*c[i][0]);  

            if(j - c[i][0] - c[i][2]>= 0)

                f[i][j] = std::max(f[i][j],f[i-1][j-c[i][0]-c[i][2]] + v[i][2]*c[i][2] + v[i][0]*c[i][0]);

            if(j-c[i][0] - c[i][1] - c[i][2] >= 0)

                f[i][j] = std::max(f[i][j],f[i-1][j-c[i][0]-c[i][1]-c[i][2]] + v[i][2]*c[i][2] + v[i][1]*c[i][1] + v[i][0]*c[i][0]);

            }
            else
                f[i][j] = f[i-1][j];
        }
    }
    printf("%d",f[m][n]);
    return 0;
}

좋은 웹페이지 즐겨찾기