hdu 4778 Gems Fight!

2572 단어 게임동적 기획dp
dp+바둑.우선 가방이 21개밖에 없는 걸 발견했어요...이렇게 하면 우리는 상태 압축으로 현재 상태에 어떤 가방이 남았는지 표시할 수 있다.그런 다음 현재 상태에 대해 두 개의 전환 방향이 있습니다.
1. 가방을 하나씩 들어라. 만약에 현재 가방이 cooker에게 영향을 준다면 우리는 마법석 tmp개를 얻을 수 있다. 그러면 다음 단계는 현재 사람이 가져간다. 그러면 dp[sta]=max(tmp+dp[sta^(12. 현재 가방이 cooker에게 영향을 주지 않는다면 다음 사람이 가장 적게 받으면 현재 사람에게 이런 상황에서 얻을 수 있는 최대치입니다.그래서 dp[sta]=max(sum-dp[sta^(1#include #include #include #include #include #include #include #include #define REP(i, n) for(int i=0; i=b; i--) #define LL long long #define PB push_back #define CLR(a, b) memset(a, b, sizeof(a)) using namespace std; const int B = 23; const int N = (1 << B); bool vis[N]; int dp[N], b, g, s, n; int sum[N], hav[B]; vector bg[B]; int calc(int tmp) { int c[B], ret = 0; CLR(c, 0); for(int i = 0 ; i < b; i ++) { if((1 << i) & tmp) { for(int j = 0; j < hav[i]; j ++) { c[bg[i][j]] ++; ret += c[bg[i][j]] / s; c[bg[i][j]] %= s; } } } return ret; } int ok(int tmp, int i) { return sum[tmp ^ (1 << i)] - sum[tmp]; } int dfs(int sta, int sum) { if(vis[sta]) return dp[sta]; vis[sta] = 1; int &ret = dp[sta]; ret = 0; for(int i = 0; i < b; i ++) { if(sta & (1 << i)) { int tmp = ok(n ^ sta, i); if(tmp) { ret = max(ret, tmp + dfs(sta ^ (1 << i), sum - tmp)); } else { ret = max(ret, sum - dfs(sta ^ (1 << i), sum)); } } } return ret; } int main() { while(scanf("%d%d%d", &g, &b, &s), b + g + s) { for(int i = 0; i < b; i ++) { scanf("%d", &hav[i]); bg[i].clear(); for(int j = 0; j < hav[i];j ++) { int tmp; scanf("%d", &tmp); bg[i].PB(tmp); } } for(int i = 1; i < (1 << b); i ++) { sum[i] = calc(i); } n = (1 << b) - 1;CLR(vis, 0); printf("%d
", 2 * dfs(n, sum[n]) - sum[n]); } }
[문제풀이] 루구4170: [CQOI2007] 색칠
Java 언어 이름 지정 안내서

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage