每周解题报告 (2nd, 8/7~8/13)

这一周主要在看 DP 的题目,嘛,都是一些我觉得很好但是我写不出来的题。本周的话做的都是 HDU 的题,虽然看了一下 Codeforces 上的一两道这样子。感觉收获还是蛮多的。

偶然学到的黑科技

在开始正式的记题之前,想先记一下这周做题和看题解的时候新学到的东西。

STL 的 unique()

STL 中提供了一个很方便的去重函数 unique(), 其功能是去除相邻的重复元素(只保留一个),所以使用前需要对数组进行排序。用 unique 之后对于有序数组就不用手动循环去重了。

STL lower_bound() 和 upper_bound()

lower_bound(arr, arr + n, val) 返回在有序数组 arr 的 [0, n) 区间中的第一个不小于 val 的值的地址。

相反的,upper_bound(arr, arr + n, val) 则返回第一个不小于 val 的值的地址。

所以,我们可以利用这个好东西:

四行写出最长上升子序列 (LIS) 的 O(nlogn) 解法

LIS 的话,传统的写法是 O(n^2) 的,用二分优化过后可以降到 O(nlogn). 至于具体的原理我就不想详细在这里记录了,不然文章又要很长。

设 arr[] 为要求 LIS 的数列,lis[] 为保存 LIS 的数组。那么我们可以通过下面的代码来求 LIS:

fill(lis, lis + n, INF);
for (int i = 0; i < n; i++)
	*lower_bound(lis, lis + n, arr[i]) = arr[i];
int len = lower_bound(lis, lis + n, INF) - lis;			// LIS 的长度

简单快捷。

4200, HDU1024, Max Sum Plus Plus

题意 & 扯淡

DP, 最大 m 子段和。没错题目很眼熟,是 P1003 的升级版,原题是最大连续子段和,这题是 n 子段和。是个挺不错的题目,之所以这么说是因为我不会它的时间和空间限制挺严格的,尤其是空间限制是 32M….emmm….

题意还是给你一个很长的数列 a1….an,然后让你找出它的 m 个子序列使得这些子序列的总和最大,输出这个总和。1 <= n <= 1e6, m 的范围未知。注意就是求出的区间不能相交。

和上一题比一个比较人道的地方就是这一题不用输出位置了。但是反而比上一题更难了。看到 32M 的内存限制,反正你想到的不是正解的解法表示状态都需要二维,肯定就 GG 了。这道题的正解是用滚动数组优化,非常巧妙,以至于我到现在还不是很理解。

说的不太清楚,如果没明白的可以看看别人写的。直接从 notepad 复制过来的,不想理通顺了,凑合着看吧。

开始正文

虽然这道题的数据范围感人,n <= 1e6, m 未知,内存 32M. 基本上告诉我们的信息就是二维的数组都开不下了,那么肯定要做一些黑科技的优化。但是这道题直接看正解是很难理解的,包括我现在看了正解还是有些地方不太明白,下面的解析是我按自己的理解 YY 的,可能有些地方并不一定对。

在正解之前,我们先来理解不做没优化的情况。如果抛开限制不谈,那么这道题的状态还是很好表示的。用 dp[i][j] 表示当子区间个数为 i,选取第 j 个数的时候的最大值。

对于 dp[i][j] 的值有两种决策:

1.将第 j 个数合并到第 i 个区间,区间个数不变,最大和为 dp[i][j-1]+a[j]. 2.将第 j 个数单独划一个区间,此时区间个数由 i-1 变为 i,最大和为当区间长度为 i-1 的时候能取到的最大值 (也就是 dp[i-1][k]) 加上 a[j].

我们可以得到这样的状态转移方程:

dp[i][j] = max(dp[i][j-1] + a[j], dp[i-1][k] + a[j]), 其中 k∈[i-1, j-1]

也即

dp[i-1][k] = max(dp[i-1][i-1], dp[i-1][i], ....., dp[i-1][j-1]).

意思是,dp[i][j] 的取值只和 dp[i][j-1] 和 dp[i-1][k] 有关。由于 i = 1 => m,那么我们事实上可以将数组降成两个一维的,也就是运用滚动数组来解这道题目:

设 d[j] 表示第 j 个数一定取的时候的最大值(dp[i][j]),premax[j] 表示 max(dp[i][i], …, dp[i][j])。那么原方程就可以化为 dp[j] = max(dp[j-1] + a[j], premax[j-1] + a[j]);

我们首先枚举区间的数量,用 curmax 表示当区间个数为 i 的时候能取得的最大值是多少,初始值为 -INF。

接着,我们枚举剩余的所有没有划分区间的数,每次枚举首先计算 dp[j],然后再将 premax[j-1] 设为 curmax,然后更新 curmax 的值为 max(curmax, dp[j]). curmax 在这里的作用就相当于表示了 max(dp[i-1][i-1], …, dp[i-1][j-1]),我们可以利用滚动数组边 DP 边计算 curmax,然后把 curmax 更新给 premax 来保存. 全部计算完之后最后的结果就是最后一次更新后的 curmax 值了。

核心的伪代码如下:

initialize curmax
for (i = 1 => m)
    let curmax = -infinity
    for (j = i => n)
        calculate dp[j] = max(dp[j-1] + a[j], premax[j-1] + a[j])
        update    premax[j-1] = curmax
        update    curmax = max(dp[j], curmax)
print curmax

代码

/**
* HDU1024 DP 最大连续 m 区间和 
*/
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e6 + 10;
const int INF = 1e9 + 7;

int n, m;
int a[MAXN];
int dp[MAXN];
int premax[MAXN];

int main()
{
  while (scanf("%d%d", &m, &n) != EOF)
  {
    for (int i = 1; i <= n; i++)
    {
      scanf("%d", &a[i]);
    }
    
    for (int i = 0; i <= n; i++)
    {
      dp[i] = 0;
      premax[i] = 0;
    }
    
 		// start solution
    int curmax;
    for (int i = 1; i <= m; i++)
    {
      curmax = -INF;
      for (int j = i; j <= n; j++)
      {
        dp[j] = max(dp[j-1] + a[j], premax[j-1] + a[j]);
        premax[j-1] = curmax;
        curmax = max(curmax, dp[j]);
      }
    }
    
    printf("%d\n", curmax);
  }
  return 0;
}

5200, HDU1028, Ignatius and the Princess III

题意 & 扯淡

依旧是 DP,虽然传闻有母函数的做法,但是本蒟蒻不知道也不会写什么母函数。题意大概就是给你一个整数 n,然后你看看这个整数 n 有多少种划分方法,例如说:

4 = 4 = 3 + 1 = 2 + 2 = 2 + 1 + 1 = 1 + 1 + 1 +1

所以 4 有 5 种划分方法。

正文

题意就是整数划分嘛,给定一个整数 n,求 n 有多少种分法,然后不能重复。

一开始都没想到是 DP 题……为什么可以用 DP 呢,一定是因为有重复计算的步骤啦。比如说我们要划分整数 4,把 4 划分到 3+1 的时候,显然 3 还能再往下划分,那么我们就可以直接利用之前已经计算过的结果了。

网上现成的 DP 题解大概有两种说法,但是状态转移方程是一样的。这个方程挺好写,但是不好想。

第一种解法是设 dp[i][j] 为将整数 i 划分为最多 j 个数的和的时候最多的方案数量。我觉得这种方案不太好理解,尤其是分类讨论的时候。所以以下分析以第二种解法为基础:设 dp[i][j] 为将整数 i 划分为不超过 j 的数的和的时候最多的方案数量。

1) 显然,当 i = 1 的时候,区间长度只能是 1,那么只有一种方法,也即 dp[1][1] = 1.

2) 当 i < j 的时候,由于不可能出现“目标数是 i,但是 j(j > i) 是 i 的一个加数”的情况,所以我们让 dp[i][j] = dp[i][i].

3) 当 i = j 的时候,dp[i][j] = dp[i][j-1] + 1

(1) 用不超过 j 的整数划分的时候,我们考虑是否要分出 j 这个数,如果要分的话由于 n = m 那么只有一种方案,就是 m 本身(对应状态转移方程中的 1),如果不分,那么就是继承 dp[i][j-1] 的结果,即把 i 分成最大加数不超过 j-1 的多少份。

(2) 如果我们用第一种解法来理解这个式子,那么 dp[i][j] = 将 i 分成 j-1 段的方案数最大值 + 将 i 分成 j 段的方案数,由于 i = j,那么将 i 分成 j 段只有一种方案,就是有 j 个 1 的情况。

4) 当 i > j 的时候,也是最不好理解的一个部分。这个时候我们可以发现一个包含 i 个数的集合 U={1, 2, 3, …, i} 可以被 j 划分为两部分:一个是 A={j},一个是 CU(A). 那么这个时候我们可以考虑是否要分出 j 这个数:如果要分出 j,那么我们只要计算剩下来的数的分离方案数,就是 dp[i-j][j];如果不分,那么答案还是把 i 分成不超过 j-1 的结果,也就是 dp[i][j-1]. 将两种方案相加,我们得到了 dp[i][j] = dp[i-j][j] + dp[i][j-1];

“这样我们就完美地解决了这个问题。”

代码

#include <bits/stdc++.h>
const int MAXN = 120 + 5;
int n;
int dp[MAXN][MAXN];

int main()
{
  while (scanf("%d", &n) != EOF)
  {
    memset(dp, 0, sizeof(dp));
    for (int i = 1; i <= n; i++)
    {
      for (int j = 1; j <= n; j++)
      {
        if (i < j)
        {
          dp[i][j] = dp[i][i];
        }
        if (i == j)
        {
          dp[i][j] = dp[i][j-1] + 1;
        }
        if (i > j)
        {
          dp[i][j] = dp[i][j-1] + dp[i-j][j];
        }
      }
    }
    printf("%d\n", dp[n][n]);
  }
  return 0;
}

6200, HDU1025 Constructing Roads In JGShining’s Kingdom

还是 DP。懒得翻题意了,自己戳原链接看好了QAQ:http://acm.hdu.edu.cn/showproblem.php?pid=1025

也就是在上文提到的最长上升子序列了,但是这一题的话用 O(n^2) 的解法是会 T 的。有两组数嘛,首先对一组排序(当然要保持和另外一组的对应关系),然后对另一组数做 LIS 就可以了。为什么是 LIS 自己画个图就知道了。

甚至可以,不用排序:在输入的时候只保存一组数据,而把另一组数作为数组的 key 即可,因为两组数是一一对应的,没有一对多的情况。

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 5 * 1e5 + 10;
const int INF = 1e9 + 10;

int n;
int ans = 0, kases = 0;
int maps[MAXN];
int dp[MAXN];
int LIS[MAXN];
int main()
{
  while (scanf("%d", &n) == 1)
  {
    kases++;
    
    // read data
    for (int i = 1; i <= n; i++)
    {
      int x, y;
      scanf("%d%d", &x, &y);
      maps[x] = y;
    }
    
    // initialize
    for (int i = 0; i <= n; i++)
    {
      dp[i] = 0;
      LIS[i] = INF;
    }
    dp[0] = 0;
    
    // LIS
    for (int i = 1; i <= n; i++)
    {
      *lower_bound(LIS + 1, LIS + 1 + n, maps[i]) = maps[i];
    }
    ans = lower_bound(LIS + 1, LIS + 1 + n, INF) - LIS - 1;
    
    printf("Case %d:\n", kases);
    printf("My king, at most %d ", ans);
    if (ans == 1)
    {
      printf("road can be built.\n");
    }
    else
    {
      printf("roads can be built.\n");
    }
    printf("\n");
  }
  
  return 0;
}

以下是自己写的时候顺手 YY 的注释:

/** * 附 nlogn 版的 LIS 写法: * 设 LIS[MAXN] 为此数列的取得 LIS 最大值时的 LIS 一种可能的情况; * 首先把 LIS 数组设为 INF:fill(LIS + 1, LIS + 1 + n, INF) ; * 然后遍历数列,利用 lower_bound 函数二分查找到 LIS 中第一个不大于 a[i] 的值的位置 pos, * 然后把 LIS[pos] 设为 a[i]. 也即 *lower_bound(LIS + 1, LIS + 1 , n, a[i]) = a[i]; * 最后统计 LIS 中不是 INF 的值的个数就可以了,即 ans = lower_bound(LIS + 1, LIS + 1 + n, INF); */

6.1, HDU1029, Ignatius and the Princess IV

之所以是 6.1 是因为这题实在是太。水。了。不是一般的水。要不是某个题目分类的帖子里说这题是 DP,我才不会做呢(

/**
* HDU1029 水题,谁说是 DP 的给我出来我保证打不死你 
* 明明是这么简单的计数题!! 
*/
#include <bits/stdc++.h> 
const int MAXN = 1e6 + 5;
int data[MAXN];
int main()
{
  int n, flag;
  while (scanf("%d", &n) != EOF)
  {
    bool state = true;
    flag = (n + 1) / 2;
    
    memset(data, 0, sizeof(data));
    
    for (int i = 0; i < n; i++)
    {
      int x;
      scanf("%d", &x);
      data[x]++;
      if (data[x] >= flag && state)
      {
        printf("%d\n", x);
        state = false;
      }
    }
  }
  return 0;
}

6.5200, HDU1232, 畅通工程

畅通工程系列的第一题,这是一道裸的并查集 OvO. 只要理解并查集的都会写啦。题目有个“温馨提示”,但是并不影响我们做题,管他什么多条道路连接的输入合不合法呢。

#include <bits/stdc++.h> 

const int MAXN = 1e3 + 10;
int p[MAXN];
int n, m;
int cnt = 0;

void init()
{
  cnt = 0;
  for (int i = 0; i < MAXN; i++)
  {
    p[i] = i;
  }
}

int find(int x)
{
  return x == p[x] ? x : p[x] = find(p[x]);
}

void unions(int x, int y)
{
  int px = find(x),
      py = find(y);
  if (px == py)
  {
    return;
  }
  else
  {
    p[px] = py;
    cnt++;
  }
}

int main()
{
  while (scanf("%d", &n) != EOF && n != 0)
  {
    init(); 
    scanf("%d", &m);
    for (int i = 0; i < m; i++)
    {
      int x, y;
      scanf("%d%d", &x, &y);
      unions(x, y);
    }
    printf("%d\n", (n - 1 - cnt));
  }
  return 0;
}

剩下的是一些旧题重做的,然后就不贴上来了。