POJ 3181 Dollar Dayz 01 전체 가방 문제
주로 몇 가지 조합이 있는지 구하는 것이다.2차원 dp로 하는 사람이 많으니 여기서 1차원 dp를 사용하면 된다.
1차원 변환 방정식: dp[j] = dp[j-i] + dp[j];그 중에서 i는 무게를 대표하고 j는 현재 가방 용량을 대표한다.
즉, dp[j-i]는 j-i 가방의 무게를 대표할 때 가장 많은 조합수를 나타낸다. 그러면 가방의 용량이 j일 때 첫 번째 아이템을 가방에 넣을 수 있다. 그러면 dp[j-i]의 종류가 있다.
만약 i 물품이 없기 전에 용량이 j일 때 조합수는 dp[j]이다.
그러면 i 물품이 있고 용량이 j일 때 조합수는 dp[j-i]+dp[j]이다.
2D에서 1D dp로 전환할 수 있는 특징:
1 현재 줄 이전의 데이터를 이용할 필요가 없다.바로 표를 작성할 때 먼저 열을 기입한 다음에 다음 줄을 기입하는 것이다.현재 줄을 기입할 때 한 줄만 데이터를 기록하면 된다.현재 열의 데이터를 즉시 읽고 덮어쓸 수 있습니다.
2 또는 역으로 표를 작성할 수 있다.현재 줄 앞의 몇 열의 데이터를 이용해야 할 때, 뒷열부터 표를 작성하는 것을 고려할 수 있다
그러나 본 문제에 대한 지식이 하나 더 생겼다. 바로 대수를 처리해야 하기 때문에 일반적인 수조로 처리하는 것도 괜찮을 것이다. 그러나 본 문제의 특징에 따라 두 개의 롱롱으로 결과를 저장할 수 있다.
#include <stdio.h>
#include <vector>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <string>
#include <limits.h>
#include <stack>
#include <queue>
#include <set>
#include <map>
using namespace std;
const int MAX_N = 1001;
int N, K;
long long hi[MAX_N], lo[MAX_N];
const long long MOD = 1E18;
int main()
{
while (~scanf("%d %d", &N, &K))
{
memset(hi, 0LL, sizeof(long long) * (N+1));
memset(lo, 0LL, sizeof(long long) * (N+1));
lo[0] = 1LL;
for (int i = 1; i <= K; i++)
{
for (int j = i; j <= N; j++)
{
hi[j] = hi[j-i] + hi[j];
hi[j] += (lo[j-i] + lo[j]) / MOD;
lo[j] = (lo[j-i] + lo[j]) % MOD;
}
}
if (hi[N] > 0LL) printf("%I64d", hi[N]);
printf("%I64d
", lo[N]);
}
return 0;
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
