UVA - 624CD(밀어냄 + 경로 인쇄)
제목 대의: 한 조의 데이터를 제시하고 N을 정하여 N보다 크지 않은 N에 가까운 데이터를 조합할 수 있는지 묻는다. 가능하면 N에 가장 가까운 데이터를 출력하고 가장 긴 경로를 출력할 수 있다(입력 순서를 찾아야 한다).
문제풀이 사고방식: dp[j]: 대표가 J라는 수치를 모으려면 최대 몇 개의 숫자가 필요하다.d【j】 = Max (d【j - v【i】】 + 1.
인쇄 경로는 최소값을 얻으면 dp가 표시한 값을 줄이면 경로를 찾을 수 있지만 최대값을 얻는다. 그러면 다음 값은 dp수 그룹의 값으로 판단할 수 없고 마지막 값이 0과 같은지 판단해야 한다.거슬러 올라가다.
코드:
#include <cstdio>
#include <cstring>
const int N = 1000005;
const int M = 25;
int visit[M];
int v[N];
int dp[N];
int n, k;
int Max (const int a, const int b) { return a > b? a: b; }
void init () {
dp[0] = 0;
for (int i = 1; i <= n; i++)
dp[i] = -1;
}
bool printf_ans (int m, int l) {
if (!m)
return true;
for (int i = l; i < k; i++)
if (m - v[i] >= 0 && dp[m - v[i]] != -1) {
visit[i] = 1;
if (printf_ans (m - v[i], i + 1))
return true;
visit[i] = 0;
}
return false;
}
int main () {
while (scanf ("%d", &n) != EOF) {
scanf ("%d", &k);
for (int i = 0; i < k; i++)
scanf ("%d", &v[i]);
init ();
for (int i = 0; i < k; i++)
for (int j = n; j >= v[i]; j--) {
if (dp[j - v[i]] != -1)
dp[j] = Max (dp[j - v[i]] + 1, dp[j]);
}
int i;
for (i = n; i >= 0; i--)
if (dp[i] != -1)
break;
memset (visit, 0, sizeof (visit));
printf_ans(i, 0);
for (int j = 0; j < k; j++)
if (visit[j])
printf ("%d ", v[j]);
printf ("sum:%d
", i);
}
return 0;
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
