这周主要是尝试了一些新的东西（ 做了一些之前一直想看但是一直没看懂和没做的题目。依旧是做 HDU 的题。虽然写得不是很熟练，不过慢慢来应该也是可以的。 另外下周由于要阶段考试这样子，可能就没有时间做题目了。
8⁄200, 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;
}
9⁄200, 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;
}
10⁄100, 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;
}
11⁄200, HDU1520, Anniversary Party
题意 & 扯淡
树形 DP 入门题，是之前突然想学学树形 DP 的时候找到的。题意大概就是一个宴会上要邀请员工，每个员工都有一个开心指数，只有在宴会上见不到自己的直属上司的时候才会开心，然后要求出开心指数的最大值。
题解
这道题有个很坑的地方就是它一个样例有好多个子任务，但是它什！么！都！没！说！ * 然后我交了 7 遍还是不知道为什么 WA 的……找了个 std 一看，卧槽要处理多组数据……
设 dp[i][0] 为不邀请第 i 个人的最大值， dp[i][1] 为邀请第 i 个人的最大值。如果我们邀请了第 i 个人，那么我们就不能邀请第 i 个人的直接下属，但是他的直接下属的下属是可以邀请的……然后按照这个思路转移方程就出来了。
首先要建树，然后这里我采用的是用图的保存方法，直接用了 vector
状态转移方程如下：
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;
}
12⁄200, 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;
}