THUSC前水题做做……

Divisors(dzi)

虽然复杂度算起来有点悬但是O(Nsqrt(A)+N^2*2^9)是可过的。

Vending Machine(aut)

首先K的范围是逗你玩的。
考虑如下策略：每次取最右侧的物品。显然不会超过40次。
也即：当K≥40*maxPrice=1600时，ans=Σ(Price*Quantity)。
那么，从后到前的朴素的O(40^3*K)就很可过了。

Bus Trip(biu)

首先肯定是先按有趣值排序然后挨个dp。
考虑转移。
如下的转移是容易想到的。

dp[x][y] = max(dp[x][y], ss.qry(x, y) + x + y);
dp[x][y] = max(dp[x][y], sr.qry(x, M + 1 - y) + x - y);
dp[x][y] = max(dp[x][y], rs.qry(N + 1 - x, y) - x + y);
dp[x][y] = max(dp[x][y], rr.qry(N + 1 - x, M + 1 - y) - x - y);
dp[x][y] += C[x][y];

ss.att(x, y, dp[x][y] - x - y);
sr.att(x, M + 1 - y, dp[x][y] - x + y);
rs.att(N + 1 - x, y, dp[x][y] + x - y);
rr.att(N + 1 - x, M + 1 - y, dp[x][y] + x + y);

但这样会TLE囧……
实际上下面这样写也是对的……

dp[x][y] = max(dp[x][y], ss + x + y);
dp[x][y] = max(dp[x][y], sr + x - y);
dp[x][y] = max(dp[x][y], rs - x + y);
dp[x][y] = max(dp[x][y], rr - x - y);
dp[x][y] += C[x][y];

ss = max(ss, dp[x][y] - x - y);
sr = max(sr, dp[x][y] - x + y);
rs = max(rs, dp[x][y] + x - y);
rr = max(rr, dp[x][y] + x + y);

因为如果要转移的那个点不在这个区域，那么在它该在的那个区域，答案会更大，所以这样做不影响正确性。
然后就消掉了两个log，然后就过了。

Sequence(cia)

水题。

DNA(dna)

这个结论暂时不会证明……就是说至少有一个最优解只由一种字符组成。

Hydra(hyd)

MemSQL, JSOI 2014, 现在又在AMPPZ看到了这道题。
总而言之，类似于最短路问题的“更新答案关系是拓扑的”的性质，这题也可以用Dijkstra一样的方法解决。
每次找临时答案最小的点确定它，一旦一个未确定点的g都被确定了就更新临时答案。

Inversions(inw)

一个块中数的肯定是连续的一段……嗯……没了。

Do It Tomorrow(jut)

最优解一定是按照Deadline顺序下来的……没了。

• 相关文章
• 全局相关文章