ZJU1027, 1074, 1076, 1093, 1100

2008年6月13日 02:23

1027是典型的两个串的DP，其实就是LCS的增强版，LCS相当于题中的表只有相等的元素值为1，其余都是0。于是按照LCS的方程做就可以了。关键问题在于边界，一定要先处理好边界（也就是一开头就是空格）的情况，这样DP才对。

#include <cstdio>
#include <cstring>

const int table[5][5]=
  {{5, -1, -2, -1, -3},
  {-1, 5, -3, -2, -4},
  {-2, -3, 5, -2, -2},
  {-1, -2, -2, 5, -1},
  {-3, -4, -2, -1, 0}};

int cases, f[101][101];

inline int max(int a, int b)
{
  return a>b?a:b;
}

int main()
{
  FILE *in = fopen("z_1027.in", "r");
  fscanf(in, "%d", &cases);
  for (int casess=0;casess<cases;casess++)
  {
    int l[2];
    char s[2][101];
    memset(s, 0, sizeof(s));
    fscanf(in, "%d %s\n", &l[0], &s[0]);
    fscanf(in, "%d %s\n", &l[1], &s[1]);
    for (int j=0;j<2;j++)
      for (int i=l[j]-1;i>=0;i--)
        s[j][i+1]=s[j][i];
    for (int j=0;j<2;j++)
      for (int i=1;i<=l[j];i++)
        switch (s[j][i])
        {
        case 'A':
          s[j][i]=0;
          break;
        case 'C':
          s[j][i]=1;
          break;
        case 'G':
          s[j][i]=2;
          break;
        case 'T':
          s[j][i]=3;
          break;
        }
    memset(f, 0, sizeof(f));
    for (int i=1;i<=l[1];i++)
      f[0][i]=f[0][i-1] + table[4][s[1][i]];
    for (int i=1;i<=l[0];i++)
      f[i][0]=f[i-1][0] + table[s[0][i]][4];
    for (int i=1;i<=l[0];i++)
      for (int j=1;j<=l[1];j++)
      {
        f[i][j]=max(f[i-1][j-1]+table[s[0][i]][s[1][j]], f[i-1][j]+table[s[0][i]][4]);
        f[i][j]=max(f[i][j], f[i][j-1]+table[4][s[1][j]]);
      }
    printf("%d\n", f[l[0]][l[1]]);
  }
}

1074是最大子矩阵，这范围太小了，随便枚举就能过。如果范围大一些可以用悬线＋单调栈来做。

#include <cstdio>

int s[100][100], n, sum, a[100][100];

inline int max(int a, int b)
{
  return a>b?a:b;
}

int getsum(int x1, int y1, int x2, int y2)
{
  if (x1!=0)
    if (y1!=0) return s[x2][y2] - (s[x1-1][y2]+s[x2][y1-1]-s[x1-1][y1-1]);
    else return s[x2][y2] - s[x1-1][y2];
  else
    if (y1!=0) return s[x2][y2] - s[x2][y1-1];
    else return a[0][0];
}

 
int main()
{
  FILE* in = fopen("z_1074.in", "r");
  fscanf(in, "%d", &n);
  for (int i=0;i<n;i++)
    for (int j=0;j<n;j++)
    {
      fscanf(in, "%d", &a[i][j]);
      if (i!=0)
        if (j!=0) s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];
        else s[i][j] = s[i-1][0] + a[i][j];
      else
        if (j!=0) s[0][j] = s[0][j-1] + a[i][j];
        else s[0][0]=a[0][0];
    }
  for (int i1=0;i1<n;i1++)
    for (int j1=0;j1<n;j1++)
      for (int i2=i1;i2<n;i2++)
        for (int j2=j1;j2<n;j2++)
          sum = max(getsum(i1, j1, i2, j2), sum);
  printf("%d\n", sum);
}

1076是相当于找出最多的不相交区间，先按右端点排序，然后就是个LIS。可以枚举起点直接贪心选择也可以DP。这题目的关键似乎在按照右端点排序这一步，因为我原来按照左端点排序就WA，改成右端点就AC，真奇怪…我觉得是等价的阿…哦，还有一个要注意的是如果DP应该把数组初始值都设为1。程序就不贴了，太丑陋了。

1093是三维的LIS的加强，而且可以旋转。旋转处理起来比较麻烦，于是干脆就把所有立方体都转好了加到里头去，然后规定不能旋转。这样就是个一般的DP了，按照第一维排序然后就很容易写方程了。一些小细节就是要事先把三维排个序，然后规定一下长宽高分别是哪个维，这样判断起来也方便DP起来也方便。

//AC
#include <cstdio>
#include <cstring>
#include <cstdlib>

int block[100][3], blocknum, n, f[100], max=0;
int cmp(const void *a, const void *b)
{
  int aa[3], bb[3];
  memcpy(aa, (int *)a, sizeof(aa));
  memcpy(bb, (int *)b, sizeof(bb));
  return (bb[0]-aa[0]);
}

void swap(int &a, int &b)
{
  int t=a; a=b; b=t;
}

void insert(int a, int b, int c)
{
  blocknum++;
  block[blocknum][0]=a;
  block[blocknum][1]=b;
  block[blocknum][2]=c;
}

int main()
{
  FILE *in = fopen("z_1093.in", "r");
  int cases=0;
  while (1)
  {
    cases++;
    fscanf(in, "%d", &n);
    if (n==0) return 0;
    memset(block, 0, sizeof(block));
    blocknum=0;
    memset(block[0], 10, sizeof(block[0]));
    for (int i=0;i<n;i++)
    {
      int a, b, c;
      fscanf(in, "%d%d%d", &a, &b, &c);
      if (a>b) swap(a, b);
      if (b>c) swap(b, c);
      if (a>b) swap(a, b);
      insert(a, b, c);
      if (a!=b)
      {
        if (c!=a) insert(b, c, a);
        if (c!=b) insert(a, c, b);
      }
      else
        if (b!=c) insert(a, c, b);
    }
    qsort(block, blocknum+1, sizeof(block[0]), cmp);
    memset(f, 0, sizeof(f));
    max=0;
    for (int i=1;i<=blocknum;i++)
      for (int j=0;j<i;j++)
        if (block[i][0]<block[j][0]&&block[i][1]<block[j][1]&&f[i]<f[j]+block[i][2])
        {
          f[i] = f[j] + block[i][2];
          max = f[i]>max?f[i]:max;
        }
    printf("Case %d: maximum height = %d\n", cases, max);
  }
}
 

1100是个状态压缩DP。按列DP，用二进制数s表示最后一列的状态（是有石头还是没有），然后DFS往上头放。这复杂度是指数级的，不过n不大没关系。我觉得程序写得异常简洁，对于一贯代码累赘的我来说…

//AC  0.07s

#include <cstdio>
#include <cstring>

long long f[2][3000], w, h;

void dfs(int pos, int cur, int next, int org)
{
  if (cur==(1<<h)-1)
  {
    if (pos!=w) f[pos&1][next] += f[(pos-1)&1][org];
    else f[pos&1][cur] += f[(pos-1)&1][org];
    return;
  }
  for (int i=0;i<h;i++)
    if ((cur&(1<<i))==0)
    {
      //yoko
      if ((next&(1<<i))==0&&pos!=w) dfs(pos, cur+(1<<i), next+(1<<i), org);
      //tate
      if (i<h-1&&(cur&(1<<(i+1)))==0) dfs(pos, cur+(1<<i)+(1<<(i+1)), next, org);
      return;
    }
}

       
int main()
{
  FILE *in = fopen("z_1100.in", "r");
  while (1)
  {
    fscanf(in, "%d%d", &w, &h);
    if (w==0) return 0;
    memset(f, 0, sizeof(f));
    f[0][0]=1;
    for (int i=1;i<=w;i++)
    {
      memset(f[i&1], 0, sizeof(f[i&1]));
      for (int j=0;j<(1<<h);j++)
        if (f[(i-1)&1][j])
          dfs(i, j, 0, j);
    }
    printf("%lld\n", f[w&1][(1<<h)-1]);
  }
}

Posted by TurtleIzzy Filed in ZOJ Tagged by DP ZJU ZOJ 程序 1027 1074 1076 1093 1100 Comments[0]

ZOJ 1013&1025

2008年6月10日 07:59

1013是说有三种兵器，每种有一个质量和一个体积还有一个防御值，然后要商队来运输，商队的每个人只能携带不超过一定质量和体积的兵器。三种兵器以某个比例和起来用可以增加防御值。求一个按照商队的限制可以得到的最大防御值。

方法应该是不难，可以用一个4维的布尔数组，第1维是商队，剩下3维表示状态，true表示这种状态可达。不过这个状态表示的效率不论空间还是时间都极低，考虑到这个布尔数组的第四维只有最大值一个点是有用的，改进一下，用3维的数组，1维是商队，剩下两维表示前两种兵器的状态，然后里头存的是在前两种兵器以及当前这个人的限制情况下，可以拿的第三种兵器的最大值。这样就可以有效降低复杂度了。

问题就是老是调不过，调不过阿调不过…

 

1025是说有一些木板，有长度和质量，要求找出递增（两个量都必须满足不小于的条件）的序列数。老题了，按两个关键字排序，然后贪心地加板子把序列弄出来就可以了。正确性可以这样看：首先，这样的贪心每一步可以得出一条长度极大的序列。这是很显然的，如果存在一条起点相同而比贪心得出的序列更长的序列B的话，那么假设B与贪心得出的序列A的第一个分叉点为C。也就是说C之前A与B都相同而C之后首次出现不同。由于贪心规测可以保证起点之后所有可以进入序列的板子都进入了，因此C不会超过起点，而起点相同，因此C不是起点，矛盾。其次，所有的序列可以用一些长度极大的序列的并表示。如果存在某个序列集，满足其中的序列数小于长度极大的序列的总数，那么其中的任何一个序列的长度一定小于相同起点的极大序列，把这些序列加起来，总长度一定小于极大序列的长度和，因此这个序列集一定不包含所有顶点。这就说明了这个贪心的正确性。

其实这个我一开始是没想到的，后来看了别人的才猛然醒悟，这题居然被归类在DP里头，于是我老是往DP方向想，囧。

Posted by TurtleIzzy Filed in ZOJ Tagged by ZJU ZOJ 1013 1025 Comments[0]