HDU 4778 Gems Fight!(dp)
2344 단어 HDU
HDU 4778 Gems Fight!
제목 링크
제목: n개의 가방이 있다. 가방에 보석이 있다. 지금 앨리스와 너는 번갈아 가방을 고르고 가방에 있는 보석을 솥에 던진다. 그리고 솥에 보석이 s개가 있다고 가정하면 마법석을 얻을 수 있다. 그리고 가방을 계속 선택할 수 있다. 두 사람은 가장 좋은 전략에 따라 가서 가장 나중에 두 사람의 마법석이 얼마나 차이가 날지 물어본다.
사고방식: dp, dp[s]는 가방 상태가 s일 때의 값을 선택한 다음에 기억화 검색을 하면 된다는 것을 의미한다. 현재 생성된 마법석을 계속 추가하지 않으면 줄일 수 있다고 가정하면 된다.
코드:#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 21;
int g, b, s, dp[(1<<N) + 5], vis[(1<<N) + 5];
int yu[(1<<N) + 5][10];
struct Page {
int num;
int a[10];
} p[N];
int cal(int S, int u) {
int ans = 0;
for (int i = 1; i <= g; i++) {
ans += (yu[S][i] + p[u].a[i]) / s;
}
return ans;
}
int dfs(int now) {
int &tmp = dp[now];
if (vis[now]) return tmp;
vis[now] = 1;
tmp = 0;
int Min = INF, Max = -INF;
if (now == (1<<b) - 1) return tmp;
for (int i = 0; i < b; i++) {
if (now&(1<<i)) continue;
int sb = cal(now, i);
int next = (now|(1<<i));
if (sb != 0) {
Max = max(Max, dfs(next) + sb);
}
else {
Min = min(Min, dfs(next));
}
}
tmp = max(Max, -Min);
return tmp;
}
int main() {
while (~scanf("%d%d%d", &g, &b, &s) && g || b || s) {
for (int i = 0; i < b; i++) {
memset(p[i].a, 0, sizeof(p[i].a));
scanf("%d", &p[i].num);
int tmp;
for (int j = 0; j < p[i].num; j++) {
scanf("%d", &tmp);
p[i].a[tmp]++;
}
}
for (int i = 0; i < (1<<b); i++) {
vis[i] = 0;
for (int j = 0; j < b; j++) {
if (i&(1<<j)) continue;
for (int k = 1; k <= g; k++) {
yu[i|(1<<j)][k] = (yu[i][k] + p[j].a[k]) % s;
}
}
}
printf("%d
", dfs(0));
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
hdu4671(다교리그 7--수 시뮬레이션)
클릭하여 링크 열기
제목:
n과 서버, m개의 데이터베이스가 있고 모든 데이터베이스는 서버를 연결해야 하지만 모든 데이터베이스는 서버를 연결하는 우선순위가 있습니다.모든 데이터베이스의 서버 우선순위를 구하다.또한 한...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 21;
int g, b, s, dp[(1<<N) + 5], vis[(1<<N) + 5];
int yu[(1<<N) + 5][10];
struct Page {
int num;
int a[10];
} p[N];
int cal(int S, int u) {
int ans = 0;
for (int i = 1; i <= g; i++) {
ans += (yu[S][i] + p[u].a[i]) / s;
}
return ans;
}
int dfs(int now) {
int &tmp = dp[now];
if (vis[now]) return tmp;
vis[now] = 1;
tmp = 0;
int Min = INF, Max = -INF;
if (now == (1<<b) - 1) return tmp;
for (int i = 0; i < b; i++) {
if (now&(1<<i)) continue;
int sb = cal(now, i);
int next = (now|(1<<i));
if (sb != 0) {
Max = max(Max, dfs(next) + sb);
}
else {
Min = min(Min, dfs(next));
}
}
tmp = max(Max, -Min);
return tmp;
}
int main() {
while (~scanf("%d%d%d", &g, &b, &s) && g || b || s) {
for (int i = 0; i < b; i++) {
memset(p[i].a, 0, sizeof(p[i].a));
scanf("%d", &p[i].num);
int tmp;
for (int j = 0; j < p[i].num; j++) {
scanf("%d", &tmp);
p[i].a[tmp]++;
}
}
for (int i = 0; i < (1<<b); i++) {
vis[i] = 0;
for (int j = 0; j < b; j++) {
if (i&(1<<j)) continue;
for (int k = 1; k <= g; k++) {
yu[i|(1<<j)][k] = (yu[i][k] + p[j].a[k]) % s;
}
}
}
printf("%d
", dfs(0));
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
hdu4671(다교리그 7--수 시뮬레이션)클릭하여 링크 열기 제목: n과 서버, m개의 데이터베이스가 있고 모든 데이터베이스는 서버를 연결해야 하지만 모든 데이터베이스는 서버를 연결하는 우선순위가 있습니다.모든 데이터베이스의 서버 우선순위를 구하다.또한 한...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.