首页 > ACM题库 > HDU-杭电 > HDU 3945-The irRegularGame of Life-动态规划-[解题报告]HOJ
2015
04-14

HDU 3945-The irRegularGame of Life-动态规划-[解题报告]HOJ

The irRegularGame of Life

问题描述 :

The irRegularGame of Life(http://www.bilibili.tv/video/av94917/) is an interesting game, it’s based on the same cell rules as Conway’s original, with the addition of limitations on initial conditions, and goals for completing levels.

The Conway’s original game of life rules is a "2-Dimensional cellular automaton". It was invented by British mathematician John Conway in 1970.It is not a game in the video game sense, but consists of a 2-D grid of cells. The game of life shouldn’t to be confused with Milton Bradley’s Board game of the same name.
Cells in the grid follow a few simple mathematical rules that determine whether they will live, die or multiply in the next generation.
Specifically, each cell interacts with its 8 horizontal, vertical, and diagonal neighbours, according to these 4 simple rules below:
1. Any live cell with fewer than 2 live neighbours dies through loneliness.
2. Any live cell with more than 3 live neighbours dies through overcrowding.
3. Any live cell with 2 or 3 live neighbours lives to the next generation.
4. Any dead cell with exactly 3 live neighbours comes to live.

DP?

Despite having such simple rules, the patterns that evolve are remarkable and can vary greatly from only small differences in initial conditions.
The game of life has fascinated mathematicians, computer scientists and nerdy types for decades.
DP?

This picture shows the rule of The irRegularGame of Life.

Sakuya thought this game is too simple, so he added some rules.
1.We have K (1<=K<=10) independent boxes in every level, and each box contains 4*4 grids.
2.The goal to pass a level is the sum of live cells in all boxes are exactly N (0<=N<=20) after T (0<=T<=200000) generations.
3.For those boxes, we can add at most M (0<=M<=20) cells.

Sakuya want know how many ways to pass one level?

As an example, initially we have one box as below.
DP?
The goal is to have exactly 5 live cells after 10 generations, and we can add at most one cell into the box.
There are 9 different ways to pass this level.

DP?

输入:

First an integer L (L <= 50), indicates there are L different levels.
For every level, the first line contains 4 integers, they are K, M, T and N which mentioned above.
Then, there are K 4*4 01-matrices follow, indicating the initial state of each box, 0 stands for an empty cell and 1 stands for an alive cell.

输出:

First an integer L (L <= 50), indicates there are L different levels.
For every level, the first line contains 4 integers, they are K, M, T and N which mentioned above.
Then, there are K 4*4 01-matrices follow, indicating the initial state of each box, 0 stands for an empty cell and 1 stands for an alive cell.

样例输入:

2

1 1 10 5
0 0 0 0
0 1 0 0
1 0 1 0
0 1 0 0

2 3 0 3
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0

样例输出:

Case #1: 9
Case #2: 4960
Hint
ATTENTION: It is to ALL the box that at most M cells are available to be add into, not to EACH box. In the second sample, we can add 3 cells into two empty boxes and the goal is the sum of live cells in all boxes are exactly 3 after 0 generation, so we have C(32,3) = 4960 different ways.


显然dp,但是其实这个题,不是考这个。。。
有了转移,发现其实重点在转移。。。
转移不小心就超时了。。。
转移就是程序里的to[k][i][j]
但是这个to是处理过来的,意思是第k个状态让i个死细胞活,最后T个周期后细胞数为j的数量
预处理是由
k状态让i个死细胞活
那么k可产生的状态为最多为(2^16)|k=0 ,然后就是怎么求解一个状态T个周期后的状态。。
这个用倍增算法即可。
所以预处理复杂度为 k * 2^16 * lg(T) 
#include <cstdio>
#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define mod 1000000009
#define pb push_back
vector <int> p[15];
int st[15];
int f[1<<16][20];
int to[15][20][20];
long long dp[15][25][25];
int num[1<<16];
int dx[]= {0,0,-1,1,1,1,-1,-1};
int dy[]= {-1,1,0,0,1,-1,1,-1};
int check(int x,int y)
{
    if(x>=0
&& x<4
&& y>=0
&& y<4)return
1;
    return 0;
}
int nxt(int t)
{
    int ret=0;
    rep(i,17)
    {
  int x=i/4;
  int y=i%4;
  int cnt=0;
  for(int j=0; j<8; j++)
  {
      int nx =
x+dx[j];
      int ny =
y+dy[j];
if(check(nx,ny))
      {
    int pos = nx*4+ny;
if((1<<pos)&t)
  cnt++;
      }
  }
if((1<<i)&t)
  {
if(cnt==2||cnt==3)
ret^=(1<<i);
  }
  else
  {
if(cnt==3)
ret^=(1<<i);
  }
    }
    return ret;
}
void init()
{
    int n =
1<<16;
memset(num,0,sizeof(num));
    rep(i,n)rep(j,17)
if(i&(1<<j))
  num[i]++;
rep(i,n)f[i][0]=nxt(i);
    for(int i=1;
i<=18; i++)
  for(int j=0; j<n; j++)
f[j][i]=f[f[j][i-1]][i-1];
}
int getnxt(int s,int t)
{
    for(int i=18;
i>=0; i–)
if((1<<i)<=t)
  {
t-=(1<<i);
s=f[s][i];
  }
    return s;
}
int main()
{
    int L,K,M,T,N,t;
    init();
scanf(“%d”,&L);
    rep(cas,L)
    {
scanf(“%d%d%d%d”,&K,&M,&T,&N);
  rep(i,K)p[i].clear();
  memset(st,0,sizeof(st));
  rep(k,K)rep(i,4)rep(j,4)
  {
scanf(“%d”,&t);
if(t)st[k]^=(1<<(i*4+j));
  }
  int n=1<<16;
  memset(to,0,sizeof(to));
  rep(k,K) // 10*2^16
rep(i,n)
if((st[k]&i) == st[k])
      {
    int j=i^st[k];
    int cnt1=num[j];
    int _nxt=getnxt(i,T);
    int cnt2=num[_nxt];
    to[k][cnt1][cnt2]++;
      }
  memset(dp,0,sizeof(dp));
  dp[0][0][0]=1;
  for(int k=0; k<K; k++)
  {
      for(int
i=0; i<=M; i++)
      {
    for(int j=0;
j<=N; j++)
    {
  if(dp[k][i][j]==0)continue;
  for(int p=0; p<=16; p++)
  {
      for(int
q=0; q<=16; q++)
      {
if(to[k][p][q]==0)continue;
    if(i+p<=M
&& j+q<=N)
dp[k+1][i+p][j+q]=(dp[k+1][i+p][j+q]+dp[k][i][j]*to[k][p][q])%mod;
      }
  }
    }
      }
  }
  long long ret=0;
  for(int i=0; i<=M; i++)
ret=(ret+dp[K][i][N])%mod;
  printf(“Case #%d: %I64d\n”,cas+1,ret);
    }
}
参考:http://blog.sina.com.cn/s/blog_7270d7f901018ajb.html


  1. 第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。

  2. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。