ZOJ 3812 We Need Medicine(모란강 온라인 게임 D 문항)
ZOJ 3812 We Need Medicine
제목 링크
사고방식: dp[i][j][k]는 i번째 아이템을 표시하고 두 개의 값이 j와 k인 상태를 구성한다. 이렇게 하면 터지기 때문에 상태를 전환해야 한다.
먼저 스크롤 그룹을 이용하면 i차원을 절약할 수 있고 j가 최대 50까지 기록되기 때문에 상태를 2진수 s로 표시하고 dp[k]=s로 전환할 수 있다. k상태를 구성하면 s를 구성할 수 있다는 뜻이다. 그러면 공간의 복잡도는 받아들일 수 있다. 그리고 이 문제의 시한은 괜찮다. 이렇게 이동한 다음에 경로를 기록하면 된다.
코드:#include <cstdio>
#include <cstring>
#include <map>
using namespace std;
const int N = 200005;
typedef unsigned long long ull;
typedef long long ll;
int t, n, q, W[N], T[N], ans[55][N];
ull dp[N];
map<ll, int> LOG;
int main() {
scanf("%d", &t);
for (int i = 0; i < 52; i++)
LOG[(1ULL<<i)] = i;
while (t--) {
scanf("%d%d", &n, &q);
memset(dp, 0, sizeof(dp));
memset(ans, 0, sizeof(ans));
dp[0] = 1;
for (int i = 1; i <= n; i++) {
scanf("%d%d", &W[i], &T[i]);
for (int j = 200000; j >= T[i]; j--) {
ull tmp = dp[j];
if (dp[j - T[i]] == 0) continue;
dp[j] |= ((dp[j - T[i]])<<W[i]) & ((1ULL<<52) - 1);
for (ull k = (tmp^dp[j]); k > 0; k &= (k - 1)) {
ll x = k;
ans[LOG[(x&(-x))]][j] = i;
}
}
}
int m, s;
for (int i = 0; i < q; i++) {
scanf("%d%d", &m, &s);
if (!ans[m][s]) printf("No solution!
");
else {
int v = ans[m][s];
int bo = 0;
while (v) {
if (bo) printf(" ");
else bo = 1;
printf("%d", v);
m -= W[v];
s -= T[v];
v = ans[m][s];
}
printf("
");
}
}
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSON
JSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다.
그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다.
저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
#include <cstdio>
#include <cstring>
#include <map>
using namespace std;
const int N = 200005;
typedef unsigned long long ull;
typedef long long ll;
int t, n, q, W[N], T[N], ans[55][N];
ull dp[N];
map<ll, int> LOG;
int main() {
scanf("%d", &t);
for (int i = 0; i < 52; i++)
LOG[(1ULL<<i)] = i;
while (t--) {
scanf("%d%d", &n, &q);
memset(dp, 0, sizeof(dp));
memset(ans, 0, sizeof(ans));
dp[0] = 1;
for (int i = 1; i <= n; i++) {
scanf("%d%d", &W[i], &T[i]);
for (int j = 200000; j >= T[i]; j--) {
ull tmp = dp[j];
if (dp[j - T[i]] == 0) continue;
dp[j] |= ((dp[j - T[i]])<<W[i]) & ((1ULL<<52) - 1);
for (ull k = (tmp^dp[j]); k > 0; k &= (k - 1)) {
ll x = k;
ans[LOG[(x&(-x))]][j] = i;
}
}
}
int m, s;
for (int i = 0; i < q; i++) {
scanf("%d%d", &m, &s);
if (!ans[m][s]) printf("No solution!
");
else {
int v = ans[m][s];
int bo = 0;
while (v) {
if (bo) printf(" ");
else bo = 1;
printf("%d", v);
m -= W[v];
s -= T[v];
v = ans[m][s];
}
printf("
");
}
}
}
return 0;
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
