每周解题报告 (3rd, 8/14~8/20)

这周主要是尝试了一些新的东西( 做了一些之前一直想看但是一直没看懂和没做的题目。依旧是做 HDU 的题。虽然写得不是很熟练,不过慢慢来应该也是可以的。 另外下周由于要阶段考试这样子,可能就没有时间做题目了。

8200, HDU5489, Removed Interval

题意 & 扯淡

题意就是已知一个数列,从中删除连续的 n 个数,然后要使得删除完之后它的最长上升子序列最大。n <= 1e5.

这题好像有很多的解法,有用传统 LIS 做的,还有用 LIS + BIT 或者 LIS + Segment Tree 做的……后面两种做法没能理解(说实话,第一种做法也没怎么能理解),所以我还是硬着头皮看了一下直接做的。

所谓题解

因为要从数列中删除一些数之后求 LIS,然后就是我们枚举删除的数的终点,然后对终点右边的第一个数为起点求一次 LIS 然后再从最左边到删除的起点求一次 最大的数不超过终点右边第一个数 的 LIS 从右往左的这个 LIS 必须在枚举起点之前预处理求出,所以: 从右往左求 LIS 可以用负数的方法来做,然后倒着求回来,一直从 n 求到 l 为止。

代码

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

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

int kases, tmp;
int n, l;
int a[MAXN], b[MAXN], dp[MAXN], LIS[MAXN];

int main()
{
  scanf("%d", &kases);
  
  while (kases--)
  {
    tmp++;
    scanf("%d%d", &n, &l);
    
    fill(dp, dp + MAXN, INF);
    
    for (int i = 0; i < n; i++)
    {
      scanf("%d", &a[i]);
      b[i] = -a[i];
    }
    
    // reverse LIS
    int pos = 0;
    fill(LIS, LIS + MAXN, INF);
    
    for (int i = l; i >= l; i--)
    {
      pos = lower_bound(LIS, LIS + n, b[i]) - LIS;
      LIS[pos] = b[i];
      dp[i] = pos + 1;
    }
    
    int ans = 0, maxlen = 0;
    fill(LIS, LIS + MAXN, INF);
    for (int i = l; i < n; i++)
    {
      pos = lower_bound(LIS, LIS + n, a[i]) - LIS;      // from left to right
      ans = max(ans, pos + 1 + dp[i] - 1);        // >=

      pos = lower_bound(LIS, LIS + n, a[i - l]) - LIS;    // update left LIS
      LIS[pos] = a[i-l];
      maxlen = max(maxlen, pos + 1);
    }
    ans = max(ans, maxlen);
    printf("Case #%d: %d\n", tmp, ans);
  }
  
  return 0;
}

9200, HDU1074, Doing Homework

扯淡

DP,而且不是一般的 DP……是状压 DP 的说。这种 DP 也不是很好理解也很难想……主要还是要写题积累经验。算是我的第一道状压吧 QAQ,之前一直以为状压 DP 涉及各种二进制和位操作挺可怕的……看理论什么的也一直看不太懂。

题解

嘛……这是我有生以来写过的第一道状态压缩 DP 的题……第一眼看到 N <= 15 就有种不好的预感 2333……

状态压缩嘛,就是把 DP 中用到的状态用二进制来表示,然后就这道题目理解了一下状态压缩 DP 的基本的写法,下面是我稍微总结的一下状态压缩 DP 的框架:

const MAXN = 最大的状态点数目
const MAXS = 1 << MAXN			// 最多的状态数,表示 2^MAXN 个
var dp[MAXS]				// DP 数组

read n

for (i = 1...(1 << n))			// 枚举每个用二进制表示的状态
    for (j = 0....n)			// 枚举每一个点
        var cur = 1 << j		// 当前点用二进制表示后的整数
	if (i & cur)			// 判断当前状态是否合法,即当前枚举的状态 (i) 必须包含当前枚举的点 (cur)
            var last = i - cur		// 这一步是可选的,如果你要获得当前状态的上一个状态
					// 那么可以用当前枚举的状态减去当前枚举的点的二进制状态

            dp equation			// 那么现在就可以开始你的 DP 方程了

print dp[(1 << n) - 1]			// 最终答案就是 dp[(1 << n) - 1] 了

然后说回到这一题上吧。题意就是某人要做好多的作业,每个作业有一个上交期限 deadline 和需要花费的时间 cost。如果每超过一天上交就扣一分,然后让你求出扣分最少的方案并输出字典序最小的方案。

由于最多只有 15 个状态点,那么用二进制表示这 15 个状态点的话,十进制的数不会超过 2^15 = 32768,所以我们想到用状压 DP 来解。那么,设整数 i 为用二进制表示了当前状态然后转换后的十进制数,然后我们就可以开一个数组 dp[1…MAXS] 来表示对于每个状态扣的分最少是多少,这里我们用二进制来表示状态,即用 0 来表示未完成这个作业,1 表示已完成这个作业。然后我们就可以从低位向高位填充来表示是否坐过这个作业了。

例如说有 5 门作业,你做了 第一门、第二门和第五门,那么用二进制表示就是 10011,然后转成十进制数就是 19.

我们用 i 枚举当前状态,然后再枚举一维 j 表示当前枚举的状态点(每一科的作业),当 i 状态包含了当前状态点的时候我们就可以根据我们的 DP 方程对 dp 数组进行更新。具体地,我们可以判断 i & (1 << j) 是否等于 1 的结果来看,如果等于 1 的话那么 i 状态就完成了第 j 门功课。

dp 方程如下(不要忘记转移的同时更新时间):

dp[i].score = dp[prev].score + max(dp[prev].time + lesson[j].cost - lesson[j].deadline, 0)

我们记 curscore = 在完成第 j 门作业前的上一个状态(可以用 i - (1 << j) 来求得上一个状态)已经花费掉的时间 + 做当前作业需要花费的时间 - 当前作业的 deadline,那么 curscore 有两种情况:1. 当 curscore > 0 的时候,就是当前决策会被扣掉的分数;2. 当 curscore <= 0 的时候,表明当前决策还不会被扣分,但是提早上交作业也不会加分,所以我们要把它设为 0.

然后呢看题目要求除了输出最小代价之外还要输出方案,那么我们可以用一个结构体来表示当个状态,除了记录代价 score 和所用时间 times 外还需要记录上一个状态 prev 和当前的科目 subject. 利用最终答案是 dp[(1 << n) - 1] 这个性质,我们就可以通过 prev 回溯回去输出方案了,具体的做法就是从最终状态往前搜寻,并把它们加入一个栈中。然后你知道怎么做了。

还有一个要注意的地方就是边界处理,不然会无限 WA。

代码

#include <bits/stdc++.h> 

using namespace std;

const int MAXN = 15;
const int MAXS = 1 << MAXN;
const int INF = 1e9 + 7;

struct Lesson {
  int deadline;
  int need;
  char name[105];
};

struct State {
  int day;
  int doing;
  int score;
  int previous;
};

Lesson les[MAXN];
State dp[MAXS];

int cases;
int n, l;

int main()
{
  scanf("%d", &cases);
  while (cases--)
  {
    memset(dp, 0, sizeof(dp));
    
    scanf("%d", &n);
    
    for (int i = 0; i < n; i++)
    {
      cin >> les[i].name >> les[i].deadline >> les[i].need;
    }
    
    int terminal = 1 << n;
    
    // state-compressing
    for (int i = 1; i < terminal; i++)
    {
      dp[i].score = INF;
      for (int j = n - 1; j >= 0; j--)
      {
        int current = 1 << j;
        if (i & current)
        {
          int prev = i - current;     // previous state
          int score = dp[prev].day + les[j].need - les[j].deadline;
          if (score < 0)
            score = 0;
            
          int newState = score + dp[prev].score;
          if (newState < dp[i].score)
          {
            dp[i].score = newState;
            dp[i].day = dp[prev].day + les[j].need;
            dp[i].previous = prev;
            dp[i].doing = j;
          }
        }
      } // for j = n-1 => 0
    } // for i = 1 => terminal
    
    printf("%d\n", dp[terminal - 1].score);
    
    // print solutions
    stack<int> solutions;
    int cur = terminal - 1;
    while (cur != 0)
    {
      solutions.push(dp[cur].doing);
      cur = dp[cur].previous;
    }
    
    while (!solutions.empty())
    {
      printf("%s\n", les[solutions.top()].name);
      solutions.pop();
    }
  }
  
  return 0;
}

10100, HDU3192, Hamburger Magi

题意 & 扯淡

第二道状压。具体的题意看题解吧,其实这些解题报告都是我把写完一题的时候 YY 出来的题解拼出来的,所以就不想浪费时间排版什么的了,看得懂找得到就行。

题解

感觉状态压缩的题目写的还是不太多,然后就没有那种感觉……不过经过上一题之后看到这道题就有些靠谱的思路了,虽然因为掉进了上一题的思维定式里然后 WA 了好几回 QAQ……

这一题的话,题意大概就是要做汉堡包,然后每个汉堡包有自己的价值 v(下文用 val 表示) 和制作所需要的能量 e(用 cost 表示),总共可以消耗的能量为 E. 再然后就是有些种类的汉堡包可能有“依赖”,也即在做他们之前需要有些汉堡包已经做好了。每种汉堡包最多做一个,然后综合上述条件,求出满足题意的最大价值 maxVal. 1 <= n <= 15.

老规律,看到 n <= 15 就想到状态压缩 DP。这道题和上一题有个比较不一样的地方在于,上一题是根据当前枚举到的状态作为已知,而当前状态的先前一个状态未知,所以是从后向前推的;这道题是把当前枚举到的状态作为已知,当前状态的下一个状态未知,然后要从前向后推。

我们记 i 为当前汉堡种类的状态,用 j 表示下一个状态相较当前状态多做的汉堡种类,在 DP 之前我们先要判断条件是否合适。由于这题当中有一个“依赖”的概念,又有一个能量的限定,所以我们在判断 DP 状态是否合法的时候要注意一下。由于前一个“依赖”的限定是硬性的,也就是这个限制只能在我们 DP 下一个状态之前先判断当前状态能否推出下一个状态;但是对于“能量”这个限定就显得比较宽松,我们既可以边 DP 边剪枝,把所需能量大于总能量的解答直接剪掉;也可以暂时不剪掉,但是记录它们的花费(尽管有时候该花费已经超过了总能量),然后在 DP 完成之后循环一遍 dp 数组,这个时候就可以很方便地根据 dp[i].cost 来判断状态是否合法了,因为这个值已经固定下来不会改变了,所以我们可以在状态合法的前提下更新答案。网上的题解大致也分这两种写法,我觉得后面一种比较好理解也好写,所以我们用第二种做法。

至于判断依赖是否满足的话,我们遍历 j 的每一个依赖 deps[j][x],如果 (i & (1 << j 的每一个依赖)),说明当前状态合法,可以由当前状态推向下一个状态;反之则不能从当前状态通过做第 j 个汉堡包达到下一个状态。

DP 方程如下,设 items[j] 为第 j 种汉堡的信息,i 为在 n 个不同的状态点的二进制状态转换成的十进制数,那么:

dp[i | (1 << j)].val = dp[i].val + items[j].val, dp[i | (1 << j)].cost = dp[i].cost + items[j].cost;

这里的 (1 << j) 表示一个“只做当前枚举的第 j 个汉堡的二进制状态”,i 是当前状态,由于 (1 << j) 二进制下只有第 j 位是 1 其他都是 0(注意这里 j 的下标是从 0 开始的),所以 i 与 1 << j 按位或返回的结果就是下一个状态。

做完 DP 之后循环一遍 dp 数组更新 ans 就可以了: ans = max(ans, dp[i].val), 其中 dp[i].cost <= E.

代码

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

const int MAXN = 15;
const int MAXS = 1 << 15;
const int INF = 1e9 + 7;

struct Hamburger {
  int val;
  int cost;
  int dep;
  int deps[15];
};
Hamburger items[MAXN];

struct State {
  int val;
  int cost;
};
State dp[MAXS];

int cases;
int n, e;

int main()
{
  scanf("%d", &cases);
  
  while (cases--)
  {
    memset(items, 0, sizeof(items));
    memset(dp, -1, sizeof(dp));
    
    scanf("%d%d", &n, &e);
    for (int i = 0; i < n; i++)
    {
      scanf("%d", &items[i].val);
    }
    for (int i = 0; i < n; i++)
    {
      scanf("%d", &items[i].cost);
    }
    for (int i = 0; i < n; i++)
    {
      scanf("%d", &items[i].dep);
      if (items[i].dep > 0)
      {
        for (int j = 0; j < items[i].dep; j++)
        {
          scanf("%d", &items[i].deps[j]);
          items[i].deps[j]--;
        }
      }
    } // end read
    
    int end = 1 << n;
    int ans = 0;

    dp[0].cost = 0, dp[0].val = 0;

    for (int i = 0; i < end; i++)
    {
      if (dp[i].cost == -1)
        continue;
        
      for (int j = 0; j < n; j++)
      {
        int cur = 1 << j;
        if (!(i & cur))
        {
          int next = i | cur;
          
          bool flag = true;
          if (items[j].dep > 0)
          {
            for (int x = 0; x < items[j].dep; x++)
            {
              int depState = 1 << items[j].deps[x];
              if (!(i & depState)) {
                flag = false;
                break;
              }
            } // for x = 0 -> items[j].dep
          } // if items[j].dep > 0
          
          if (flag)
          {
            dp[next].val = dp[i].val + items[j].val;
            dp[next].cost = dp[i].cost + items[j].cost;
          }
          
        } // if i & cur
      } // for j = 0 -> n
    } // for i = 1 -> end

    for (int i = 0; i < end; i++)
    {
      if (dp[i].cost <= e)
        ans = max(ans, dp[i].val);
    }
  
    printf("%d\n", ans);

  }
  
  return 0;
}

11200, HDU1520, Anniversary Party

题意 & 扯淡

树形 DP 入门题,是之前突然想学学树形 DP 的时候找到的。题意大概就是一个宴会上要邀请员工,每个员工都有一个开心指数,只有在宴会上见不到自己的直属上司的时候才会开心,然后要求出开心指数的最大值。

题解

这道题有个很坑的地方就是它一个样例有好多个子任务,但是它什!么!都!没!说! * 然后我交了 7 遍还是不知道为什么 WA 的……找了个 std 一看,卧槽要处理多组数据……

设 dp[i][0] 为不邀请第 i 个人的最大值, dp[i][1] 为邀请第 i 个人的最大值。如果我们邀请了第 i 个人,那么我们就不能邀请第 i 个人的直接下属,但是他的直接下属的下属是可以邀请的……然后按照这个思路转移方程就出来了。

首先要建树,然后这里我采用的是用图的保存方法,直接用了 vector[MAXN] 数组来存第 i 个人的直接下属。首先找到树根,也就是入度为 0 的(没有父亲或者说父亲是本身的)那个节点 Q,然后以此节点为起点做一遍 DFS,边 DFS 边状态转移,之后输出答案就好了。

状态转移方程如下:

dp[i][0] = max(dp[k1][0], dp[k1][1]) + ... + max(dp[kx][0], dp[kx][1])
// 其中 k1 ... kx 是第 i 个员工的所有直属下属的下标

dp[i][1] = dp[k1][0] + dp[k2][0] + ... + dp[kx][0]
// 假如第 i 个员工要出席宴会,这种情况下他的直接下属都不能参加

然后答案就是 ans = max(dp[Q][0], dp[Q][1]);.

代码

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

const int MAXN = 6010;
int n;
int rate[MAXN], p[MAXN];
int dp[MAXN][2];
vector<int> T[MAXN];

void dfs(int s)
{
  if (T[s].size() == 0)
  {
    dp[s][1] = rate[s];
    dp[s][0] = 0;
    return;
  }
  
  for (int i = 0; i < T[s].size(); i++)
  {
    int cur = T[s][i];
    dfs(cur);
    dp[s][0] += max(dp[cur][1], dp[cur][0]);
    dp[s][1] += dp[cur][0];
  }
  dp[s][1] += rate[s];
  return;
}

int main()
{
  while (scanf("%d", &n) != EOF)
  {
    memset(rate, 0, sizeof(rate));
    memset(p, 0, sizeof(p));
    memset(dp, 0, sizeof(dp));
    
    for (int i = 0; i <= MAXN; i++)
    {
      T[i].clear();
    }
    
    for (int i = 1; i <= n; i++)
    {
      scanf("%d", &rate[i]);
    }
    
    int x, y;
    while (scanf("%d%d", &x, &y) != EOF && x != 0 && y != 0)
    {
      T[y].push_back(x);
      p[x] = y;
    }
    
    int s;
    for (int i = 1; i <= n; i++)
    {
      if (p[i] == 0)
      {
        s = i;
        break;
      }
    }
    
    dfs(s);
    int ans = max(dp[s][0], dp[s][1]);
    printf("%d\n", ans);    
  }
  return 0;
}

12200, HDU1166, 敌兵布阵

题意自己看原题吧 Orz 反正是中文的,这题用 BIT 和单点修改的线段树都可以做,是个裸的板子题。记一下这道题的板子代码以防将来需要。

BIT version

因为只有单点修改,所以用树状数组完全可以胜任。

#include <bits/stdc++.h>

const int MAXN = 50005;
int n;
int c[MAXN];

int lowbit(int x)
{
  return x & (-x);
}

void add(int i, int value)
{
  while (i <= n)
  {
    c[i] += value;
    i += lowbit(i);
  }
}

int sum(int x)
{
  int res = 0;
  while (x > 0)
  {
    res += c[x];
    x -= lowbit(x);
  }
  return res;
}

int main()
{
  int t;
  scanf("%d", &t);
  
  for (int i = t; i > 0; i--)
  {
    printf("Case %d:\n", t - i + 1);
    scanf("%d", &n);
    memset(c, 0, sizeof(c));
    
    for (int j = 1; j <= n; j++)
    {
      int x;
      scanf("%d", &x);
      add(j, x);
    }
    
    char str[10];
    int x, y;
    while (scanf("%s", str) != EOF && str[0] != 'E')
    {
      scanf("%d%d", &x, &y);
      
      if (str[0] == 'Q') {
        int res = sum(y) - sum(x-1);
        printf("%d\n", res);
      }
      
      if (str[0] == 'A') {
        add(x, y);
      }
      
      if (str[0] == 'S') {
        add(x, -y);
      }
    }
    
  }
  
  return 0;
}

Segment Tree version

线段树的单点修改区间查询版也可以做这题,如下。写起来会比树状数组的版本麻烦一些。记得一个很重要的地方就是线段树的数组要开到 MAXN 的 4 倍。

#include <bits/stdc++.h> 
const int MAXN = 50010;

int n;
int kases, tmp;

struct SegTree
{
  int sum[MAXN << 2];
  
  void pushUp(int root) 
  {
    sum[root] = sum[root * 2] + sum[root * 2 + 1];
  }
  
  void build(int left, int right, int root)
  {
    if (left == right)
    {
      scanf("%d", &sum[root]);
      return;
    }
    int middle = (left + right) / 2;
    build(left, middle, root * 2);
    build(middle + 1, right, root * 2 + 1); 
    
    pushUp(root);
  }
  
  void update(int left, int right, int root, int pos, int addVal)
  {
    if (left == right)
    {
      sum[root] += addVal;
      return;
    }
    int middle = (left + right) / 2;
    
    if (pos <= middle)
    {
      update(left, middle, root * 2, pos, addVal);
    }
    else
    {
      update(middle + 1, right, root * 2 + 1, pos, addVal);
    }
    
    pushUp(root);
  }
  
  int query(int from, int to, int left, int right, int root)
  {
    if (from <= left && right <= to)
    {
      return sum[root];
    }
    
    int middle = (left + right) / 2;
    
    int res = 0;
    if (to <= middle)
    {
      res += query(from, to, left, middle, root * 2);
    }
    else if (from > middle)
    {
      res += query(from, to, middle + 1, right, root * 2 + 1);
    }
    else
    {
      res += query(from, to, left, middle, root * 2) + query(from, to, middle + 1, right, root * 2 + 1);
    }
    
    return res;
  }
  
  void init()
  {
    for (int i = 0; i < MAXN; i++)
    {
      sum[i] = 0;
    }
  }
};

SegTree tree;

int main()
{
  scanf("%d", &kases);
  
  while (kases--) 
  {
    tmp++;
    printf("Case %d:\n", tmp);
    
    scanf("%d", &n);
    
    tree.init();
    tree.build(1, n, 1);
    
    char commands[20];
    while (scanf("%s", commands) != EOF && commands[0] != 'E')
    {
      if (commands[0] == 'Q')
      {
        int x, y;
        scanf("%d%d", &x, &y);
        
        int res = tree.query(x, y, 1, n, 1);
        printf("%d\n", res);
      }
      
      if (commands[0] == 'A')
      {
        int x, y;
        scanf("%d%d", &x, &y);
        tree.update(1, n, 1, x, y);
      }
      
      if (commands[0] == 'S')
      {
        int x, y;
        scanf("%d%d", &x, &y);
        tree.update(1, n, 1, x, -y);
      }
    }
  }
  
  return 0;
}