250. PiecewiseLinearFunction

Brief description:

… 给定一个分段线性 (piecewise linear) 函数。。
。。问 f(x) = k 最多可以有多少个解 （k∈R）。若可以有无限多解则返回 -1。

Analysis:

先判断无解。。然后线段树求最大覆盖次数。。注意端点处只被覆盖一次。需要开始全部*2然后拆点。
。。当然这种预处理后一次询问的问题。。可以用离线算法 ———— +1-1 标记数组 + 排序来解决。。
。。当然 O(n2) 暴力不容易写错。。。

500. History

Brief description:

… 有 n 个国家。。每个国家有一些朝代。朝代都是从 0 开始纪年。
。。给定每个朝代的持续时间，两个朝代被称为同时代的。。如果这两个朝代中存在一对纪年表示的是同一年。
。现在给定一些同时代关系。。问是否另一些朝代之间也可能是同时代的。。。

Analysis:

。。差分约束模型。。

1000. StringWeight

Brief description:

… 一个字符串含有 26 个英文字母。。一个字符串的权值。。记作所有至少出现过一次的字符、出现的最右边位置减去最左边位置。。。
。。一个字符串被称为是 “轻的”。。如果在所有相同长度的字符串中。。没有权值比它更小的。。。。
现在给定一个数组 L[0], L[1], … L[n-1] …
要求你用长度分别为 L[0], L[1], … L[n-1] 的 “轻的” 字符串依次连接成一个大字符串。。。
、。。。最小化这个大字符串的权值。。

Analysis:

… 首先。。对于一个 “轻的” 字符串。。一定要最大限度的用满 26 的字符。。
。。然后重复多次的字符。。一定都是在一块连续的位置。。。

当我们以及处理了一部分字符串。。。考察下一个字符串的某个字符时。。它可能处于以下三种状态之一：

白色 (White)：尚未出现。
灰色 (Gray): 已经出现。
黑色 (Black): 已经终止。

知道其中两个就行了。。

我们有 White -> Gray, Gray -> Black 以及在当前这个字符串中直接 White -> Black 三种转移。。
这些需要枚举。。。

。。YY 出状态。。以每一段小字符串划分阶段。。。

const int N = 60, Z = 27;
int dp[N][Z][Z]; //Gray, White

class StringWeight {
public:
  int getMinimum(vector <int> L) {

	    int n = SZ(L); FLC(dp, 0x3f), dp[0][0][26] = 0;

	    REP_3(i, j, k, n, 27, 27) if (dp[i][j][k] != INF){
	        REP_2(jj, kk, j+1, k+1){ // Black, Gray ..
	            if (j + kk < min(26, L[i]) || jj + kk > L[i]) continue;
	            int b = dp[i][j][k] + (jj-1)*jj/2 + (j-jj)*L[i];
	            if (jj + kk == 26) b += L[i] - 26;
	            REP(jjj, kk+1) checkMin(dp[i+1][j-jj+jjj][k-kk], b += jjj);
	        }
	    }

		int res = INF; REP_2(i, j, Z, Z) checkMin(res, dp[n][i][j]);
		return res;
	}
};

dp[i][j][k]: 表示当前考察到第 i 个字符串，j 个灰色字符，k 个白色字符的最小权值。
。。状态 O(NZ^2) 。。转移 O(Z^3)。。

来具体分析转移。。Gray -> Black 一定是从最左边开始关闭。。所以加等差数列 (jj-1)*jj/2 即可。
Gray -> Gray 。。比较糟糕。。每一类都要增加 L[i] 的损耗。。
White -> Black 。。无损耗。
White -> Gray 。。这类尽量往右边填。。也是一个等差数列。。。

External link:

https://apps.topcoder.com/wiki/display/tc/SRM+586
https://gist.github.com/lychees/6140957

Posted by xiaodao
Category: TopCoder