Kyrieh Girls 2007-2008

状态压缩……写得巨恶心无比，要是WA了或者T了之类我还真不知该怎么办欧……
预处理写到我崩溃，代码巨长，速度垫底，还不如不写呢……

33

2785080

hellengine

33388K

9515MS

G++

4092B

2007-10-13 21:10:28

庆Shanghai 2004割通啊～～

	2280	Amphiphilic Carbon Molecules	70	Shanghai 2004
	2281	Link and Pop -- the Block Game	32	Shanghai 2004
	2282	The Counting Problem	415	Shanghai 2004
	2283	Different Digits	178	Shanghai 2004
	2284	That Nice Euler Circuit	107	Shanghai 2004
	2285	The Floor Bricks	34	Shanghai 2004
	2286	The Rotation Game	86	Shanghai 2004
	2287	Tian Ji -- The Horse Racing	477	Shanghai 2004
	2288	Islands and Bridges	163	Shanghai 2004
	2289	Jamie's Contact Groups	142	Shanghai 2004

以及POJ第1500次提交～小小地开心一下～

2785080

hellengine

2285

Accepted

33388K

9515MS

G++

4092B

2007-10-13 21:10:28

代码～～

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cctype>
using namespace std;

const int mmx = 1010;
const int LIM = (1 << 15);
const int inf = (int)1e9;

short int trans[LIM][1 << 9];
int gil[1 << 9], block[1 << 9], cnt, fl[mmx], f[2][LIM], S, N, M;
char ss[5][5];

void init();
void prep();
void work();

void make_block(int& v, int x0, int y0, int dx, int dy, int arg)
{
  v = 0;
  for(int i = 0; i < 3; i++)
    for(int j = 0; j < 3; j++) {
      int tx = x0 + (arg ? i * dx : j * dx);
      int ty = y0 + (arg ? j * dy : i * dy);
      if(ss[tx][ty] == '#') v += (1 << (i * 3 + j));
    }
}

void print_block(int v)
{
  for(int i = 2; i >= 0; i--) {
    for(int j = 0; j < 3; j++) {
      int t = (v & (1 << (i + j * 3)));
      printf("%c", t ? '#' : '.');
    }
    printf("\n");
  }
  printf("\n");
}

void print_state(int v)
{
  for(int i = 4; i >= 0; i--) {
    for(int j = 0; j < 3; j++) {
      int t = (v & (1 << (i + j * 5)));
      printf("%c", t ? '#' : '.');
    }
    printf("\n");
  }
  printf("\n");
}

void place_block(int st, int b, int pos, int& new_st)
{
  int new_b(0), hig(0);

  for(int i = 0, j = 0; i < 9; i++, j++) {
    if(b & (1 << i)) {
      new_b += (1 << j);
      hig >?= i % 3;
    }
    if(i % 3 == 2) j += 2;
  }

  if(0 > pos || (hig + pos >= 5) || (st & (new_b <<= pos))) new_st = 0;
  else new_st = (st | new_b);
}

inline int make_floor(int hig)
{
  int ret(0);
  for(int i = hig; i < 5; i++) ret += (1 << (i + 10));
  return ret;
}

inline int get(int v, int p1, int p2, int p3)
{
  return (v & (1 << p1)) || (v & (1 << p2)) || (v & (1 << p3));
}

int main()
{
  while(1 == scanf("%d", &N) && N) {
    init();
    prep();
    work();
  }
  return 0;
}

void init()
{
  int lst[5], t_gil;

  fill_n(fl, mmx, 0);
  fill_n(gil, (1 << 9), inf);
  cnt = 0;

  for(int i = 0; i < N; i++) scanf("%d", &fl[i]);
  while(N < 3) fl[N++] = 0;

  S = 0;
  for(int i = 0; i < 3; i++) S = (S >> 5) + make_floor(fl[i]);
  
  scanf("%d", &M);

  for(int i = 0; i < M; i++) {
    scanf("%d", &t_gil);
    for(int j = 0; j < 3; j++) scanf("%s", ss[j]);
    make_block(lst[0], 0, 0, 1, 1, 1);
    make_block(lst[1], 0, 2, 1, -1, 0);
    make_block(lst[2], 2, 2, -1, -1, 1);
    make_block(lst[3], 2, 0, -1, 1, 0);
    if(!lst[0]) continue;
    for(int j = 0; j < 4; j++) {
      while(!get(lst[j], 0, 1, 2)) lst[j] >>= 3;
      while(!get(lst[j], 0, 3, 6)) lst[j] >>= 1;
      if(gil[lst[j]] == inf) block[cnt++] = lst[j];
      gil[lst[j]] <?= t_gil;
    }
  }
}

void prep()
{
  int pos, new_st;

  for(int i = 0; i < LIM - 1; i++) {
    for(pos = 0; pos < 5; pos++) if(!(i & (1 << pos))) break;
    if(pos == 5) continue;
    for(int j = 0; j < cnt; j++) {
      trans[i][j] = 0;
      for(int k = 0; k > -3; k--) if(block[j] & (1 << (0 - k))) {
    place_block(i, block[j], pos + k, new_st);
    if(new_st & (1 << pos)) trans[i][j] = new_st;
      }
    }
  }
}

void work()
{
  int p(0), q(1);
 
  fill_n(f[0], 2 * LIM, inf);
  f[0][S] = 0;

  for(int i = 0; i < N; i++, p = !p, q = !q)
    for(int j = 0; j < LIM; j++) if(f[p][j] < inf) {
      if((j & 31) == 31) f[q][(j >> 5) + make_floor(fl[i + 3])] <?= f[p][j];
      else for(int k = 0; k < cnt; k++) if(trans[j][k])
    f[p][trans[j][k]] <?= f[p][j] + gil[block[k]];
      f[p][j] = inf;
    }

  if(f[p][LIM - 1] == inf) printf("Impossible.\n");
  else printf("Need at least %d Gil(s).\n", f[p][LIM - 1]);
}