练习题 - 制作唱片(动态规划)

前言

算法拾遗继续。

题目

你刚刚继承了n首珍贵的、没有发行的歌曲,它们由流行的演唱组Raucous Rockers录制。 你的计划是选择其中一些歌曲来发行m个唱片, 每个唱片至多包含t分钟的音乐, 唱片中的歌曲之间不能重复。 由于你是一个古典音乐的爱好者,所以你没办法区分这些歌曲的价值,你按 照下面的标准作选择: 1) 这些唱片中的歌曲必须按它们写作的顺序排序。(如果第一个唱片录 制了歌曲1、3,则第二个唱片只能从4开始选择) 2)包含歌曲的总数量尽可能的多。 输入:第一行包含数值n,t,m(不大于20的整数),下面包含n首歌 曲的长度,它们按写作的顺序排列,没有一首歌曲超出唱片的长度,而 且不可能将所有歌曲都放在唱片中。

输出:

输出应是按照标准进行选择m个唱片,所能包含的最多歌曲数目。

样例: 输入:

5 6 4 
4 3 4 4 5

输出:

4

解答

#include <stdio.h>

FILE *in, *out;
int n, t, m, a[21], b[21][21] = {0}, copy[21], yige[21][21] = {0}, min = 20;

void clear() {
  int i;
  for (i = 0; i <= 21; i++)
    copy[i] = 0;
}

void docopy(int i, int j) {
  int k, wz = 1;
  for (k = i; k <= j; k++)
    copy[wz++] = a[k];
}

void swap(int i, int j) {
  int tem;
  tem = copy[i];
  copy[i] = copy[j];
  copy[j] = tem;
}

void paixu(int len) {
  int i, j;
  for (i = 1; i < len; i++)
    for (j = i + 1; j <= len; j++)
      if (copy[j] < copy[i])
        swap(i, j);
}

int qiuyige(int i, int j) {
  int tem = 0, max = 0, k;
  clear();
  docopy(i, j);
  paixu(j - i + 1);
  for (k = 1; k <= j - i + 1; k++) {
    tem += copy[k];
    if (tem > t)
      return (k - 1);
  }
  return (j - i + 1);
}

int main() {
  in = fopen("C.in", "r");
  fscanf(in, "%d%d%d", &n, &t, &m);
  int i;
  for (i = 1; i <= n; i++)
    fscanf(in, "%d", &a[i]);
  fclose(in);

  /*
  for(i=1;i<=n;i++)
     printf("%5d ",a[i]);
  printf("\n");
  getchar();*/

  int j, k;
  for (i = 1; i <= n; i++)
    for (j = i; j <= n; j++)
      yige[i][j] = qiuyige(i, j);

  for (i = 1; i <= n; i++)
    b[i][1] = yige[1][i];

  int tem, max, l;
  for (k = 2; k <= m; k++)
    for (i = k; i <= n; i++) {
      max = 0;
      for (l = k; l <= i; l++) {
        tem = b[l - 1][k - 1] + yige[l][i];
        if (tem > max)
          max = tem;
      }
      b[i][k] = max;
    }

  /* printf("------------");getch();
   for(j=1;j<=m;j++)
      {for(i=1;i<=n;i++)
         printf("%5d",b[i][j]);
       printf("\n");
      }
   getchar();*/

  out = fopen("C.out", "w");
  fprintf(out, "%d", b[n][m]);
  fclose(out);

  return 0;
}

参考


* cached version, generated at 2018-12-08 23:46:51 UTC.

Subscribe by RSS