动态规划算法之多边形游戏

/*
 * Filename: poly_max.c
 *
 * Function: 这是1998年国际信息学奥林匹克竞赛题
 *           题目大意是，给定一个序列，由符号和数字组成，其中的符号只有+和*，
 *           数字有正有有负，这样可以构成一个由符号与数字相间的一个环，
 *           现在从任意的一个符号断开，断开后则为一个表达式，
 *           我们可以通过对其加括号的方式求得一个最大的值，比如"*7+4+-2*5"，
 *           我们从第一个+号断开，则剩下7+4+-2*5,如果我们这样加括号7+4+(-2*5)
 *           得到结果为1，如果这么加(7+4-2)*5得到45，如果我们不从7前面的*断开，
 ＊          而从4前面的+断开，则构成4+-2*5*7，通过(4+-2)*5*7得到70,实际上，
 *           它为本程序的解。
 *
 * Note:     (1)本程序不检查输入错误，错误的输入可能导致程序崩溃
 *           (2)输入应该以符号开始，以数字结尾
 *           (3)为了简化程序，这里假定输入的数字不会超过10，即最多9个符号
 *           (4)多个数字连在一起当作一个整数计算
 *
 * Version: 1.1
 *
 * Author: WUSW
 * Date:   2009.4.26
 */


#include
#include
#include

#define NUM 10            /*limit the number of input integers */

/**************** LIST ****************/
/*为了缩减代码，这里符号和数据都用同一种数据结构存贮的，所以我在这里用0来代表+,1来代表* */
typedef struct NODE
{
  int elem;            /* for symbol: 0 represent '+' and 1 for '*'
                   for data: some are positive and others are
                   negative */
  int flag;            /* to indicate whether it is calculated
                   因为每个符号都可以作为最初断开的地方，由于符号是用
                   链表存贮的，处理完一个符号就将其放在链表的末尾，并
                   且将此标记记为1，这样，当遇到有一个符号，它的此
                   标记为1时，代表所有符号都已经处理完毕*/
  size_t len;            /* only used by head to indicate the length
                   of the list, then allocate an array according to it */
  struct NODE *tail;        /* only used by head node
                   to point to  the last elem */
  struct NODE *next;
}NODE;

void init_node(NODE *n)
{
  n->elem = 0;
  n->flag = 0;
  n->len = 0;
  n->tail = n;
  n->next = NULL;
}

void add_elem(NODE *n, int elem)
{
  NODE *adder;
 
  while (NULL == (adder=calloc(1,sizeof(NODE))));
  init_node(adder);
  adder->elem = elem;
  n->tail->next = adder;
  n->tail = adder;
  n->len++;
}

void free_node(NODE *n)
{
  while (n != NULL)
    {
      free(n);
      n = n->next;
    }
}

/**************** algorithm ****************/

/* get the max and min value
   we should pay attention to multiplication*/
void max_min(NODE *smp, int i, int j, int k, int *max, int *min,
         int m[NUM][NUM][2])
{
  int a = m[i][k][0];
  int b = m[i][k][1];
  int c = m[k+1][j][0];
  int d = m[k+1][j][1];
  int tmp[4];

  NODE *n = smp->next;
  int x = 0;
 
  for (x=0; x    {
      n = n->next;
    }
   
  if (n->elem == 0)
    {
      *max = a + c;
      *min = b + d;
    }
  else
    {
      tmp[0] = a * c;
      tmp[1] = a * d;
      tmp[2] = b * c;
      tmp[3] = b * d;

      *max = tmp[0];
      *min = tmp[0];

      int i = 0;
      for (i=1; i<4; i++)
    {
      if (*max < tmp[i])
        {
          *max = tmp[i];
        }
      if (*min > tmp[i])
        {
          *min = tmp[i];
        }
    }
    }
}

 
int poly_max(NODE *smb, NODE *data)
{
  int m[NUM][NUM][2] = {{{0}}};
  int i = 0;
  int j = 0;

  NODE *p = data->next;
 
  for (i=0; ilen; i++)
    {
      m[i][i][0] = p->elem;
      m[i][i][1] = p->elem;
      p = p->next;
    }
 
  int span = 2;
  int k = 0;
  int max = 0;
  int min = 0;
 
  for (span=2; span<=data->len; span++)
    {
      for (i=0; i<=data->len-span; i++)
    {
      j = i + span -1;
      max_min(smb, i, j, i, &max, &min, m);
      m[i][j][0] = max;
      m[i][j][1] = min;
     
      for (k=i+1; k        {
          max_min(smb, i, j, k, &max, &min,  m);

          if (m[i][j][0] < max)
        {
          m[i][j][0] = max;
        }
          if (m[i][j][1] > max)
        {
          m[i][j][1] = min;
        }
        }
    }
    }
  return m[0][data->len-1][0];
 
}

void output(NODE *n)
{
  while (n != NULL)
    {
      printf("%d ", n->elem);
      n = n->next;
    }

  printf("\n");
}

/* to store the given datas and symbols with two lists */
void init(char *str, NODE *smb, NODE *data)
{
  init_node(smb);
  init_node(data);

  int sign = 1;
 
  while (*str != '\0')
    {
      switch (*str)
    {
    case '+':
      add_elem(smb, 0);
      str++;
      break;
    case '-':
      sign = -1;
      str++;
      break;
    case '*':
      add_elem(smb, 1);
      str++;
      break;
    default:
      add_elem(data, sign*atoi(str));
      while (isdigit(*str))
        {
          str++;
        }
      sign = 1;
      break;
    }
    }
}

/* disconnect the list at any symbol, and return the max value */
int count(NODE *smb, NODE *data)
{
  int max = -32767;
  int temp;
 
  NODE *tmp = smb->next;
  NODE *d = data->next;
 
  while (tmp->flag != 1)
    {
      /*move the first operator to the end first for it begins with operator */
      tmp->flag = 1;
      smb->next = tmp->next;
      smb->tail->next = tmp;
      tmp->next = NULL;
      smb->tail = tmp;
  
      temp = poly_max(smb, data);

      max = max     
      tmp = smb->next;

      /*move the first data to the end */
      data->next = d->next;
      data->tail->next = d;
      d->next = NULL;
      data->tail = d;
      d = data->next;
    }

  free_node(smb->next);
  free_node(data->next);
 
  return max;
}

int main(int argc, char * argv[])
{
 
  char *str = "*7+4+-2*5";

  NODE smb;
  NODE data;
 
  init(str, &smb, &data);
 
  printf("%d\n",  count(&smb, &data));

 
  return 0;
}