김명의 예산 방안[동태 기획]
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;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[NOIP2017 A팀 합숙훈련 향상 10.22] 우정.Flowey는 우정의 알갱이를 통해 LOVE를 전파할 수 있는 작은 꽃이다. 우정의 알갱이는 두 가지로 나뉘는데, 둥근 알갱이와 구겨진 알갱이가 순서대로 배열되어 길이가 2m의 서열을 이루고 있다. 우정의 알갱이에 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.