Codeforces Round #461 (Div. 2) 题解
比赛地址:Dashboard – Codeforces Round #461 …
May all the beauty be blessed.
题目地址:洛谷:【P1070】道路游戏 – 洛谷
小新正在玩一个简单的电脑游戏。
游戏中有一条环形马路,马路上有 n 个机器人工厂,两个相邻机器人工厂之间由一小段马路连接。小新以某个机器人工厂为起点,按顺时针顺序依次将这 n 个机器人工厂编号为1~n,因为马路是环形的,所以第 n 个机器人工厂和第 1 个机器人工厂是由一段马路连接在一起的。小新将连接机器人工厂的这 n 段马路也编号为 1~n,并规定第 i 段马路连接第 i 个机器人工厂和第 i+1 个机器人工厂(1≤i≤n-1),第 n 段马路连接第 n 个机器人工厂和第 1个机器人工厂。
游戏过程中,每个单位时间内,每段马路上都会出现一些金币,金币的数量会随着时间发生变化,即不同单位时间内同一段马路上出现的金币数量可能是不同的。小新需要机器人的帮助才能收集到马路上的金币。所需的机器人必须在机器人工厂用一些金币来购买,机器人一旦被购买,便会沿着环形马路按顺时针方向一直行走,在每个单位时间内行走一次,即从当前所在的机器人工厂到达相邻的下一个机器人工厂,并将经过的马路上的所有金币收集给小新,例如,小新在 i(1≤i≤n)号机器人工厂购买了一个机器人,这个机器人会从 i 号机器人工厂开始,顺时针在马路上行走,第一次行走会经过 i 号马路,到达 i+1 号机器人工厂(如果 i=n,机器人会到达第 1 个机器人工厂),并将 i 号马路上的所有金币收集给小新。 游戏中,环形马路上不能同时存在 2 个或者 2 个以上的机器人,并且每个机器人最多能够在环形马路上行走 p 次。小新购买机器人的同时,需要给这个机器人设定行走次数,行走次数可以为 1~p 之间的任意整数。当马路上的机器人行走完规定的次数之后会自动消失,小新必须立刻在任意一个机器人工厂中购买一个新的机器人,并给新的机器人设定新的行走次数。
以下是游戏的一些补充说明:
现在已知每段马路上每个单位时间内出现的金币数量和在每个机器人工厂购买机器人需要的花费,请你告诉小新,经过 m 个单位时间后,扣除购买机器人的花费,小新最多能收集到多少金币。
输入格式:
第一行 3 个正整数,n,m,p,意义如题目所述。
接下来的 n 行,每行有 m 个正整数,每两个整数之间用一个空格隔开,其中第 i 行描述了 i 号马路上每个单位时间内出现的金币数量(1≤金币数量≤100),即第 i 行的第 j(1≤j≤m)个数表示第 j 个单位时间内 i 号马路上出现的金币数量。
最后一行,有 n 个整数,每两个整数之间用一个空格隔开,其中第 i 个数表示在 i 号机器人工厂购买机器人需要花费的金币数量(1≤金币数量≤100)。
输出格式:
共一行,包含 1 个整数,表示在 m 个单位时间内,扣除购买机器人花费的金币之后,小新最多能收集到多少金币。
输入样例#1:
2 3 2 1 2 3 2 3 4 1 2
输出样例#1:
5
【数据范围】
对于 40%的数据,2≤n≤40,1≤m≤40。
对于 90%的数据,2≤n≤200,1≤m≤200。
对于 100%的数据,2≤n≤1000,1≤m≤1000,1≤p≤m。
NOIP 2009 普及组 第四题
这里我采用的是GhastIcon同学的思路。可以在这里P1070 道路游戏 题解找到他的题解。
设计状态dp[i]为到第i时刻获得的最大金币数,转移可以通过枚举这个时刻到的位置和走过的步数来实现,方程如下
dp[i] = \max \{dp[i - t] + g[i][s - 1] - g[i][s - t - 1] - c[s - t]\}
具体解释一下上面的各个变量。t是枚举的步数,s是枚举的当前位置。i-t表示t时间前的时刻,p-t表示t时间前的位置(要注意处理一下让它在1~n范围内),g表示一种斜线的前缀和,c表示在这个位置买机器人的开销。可以知道我们的收益在题目给的那个表上是对角线上计算的,以样例为例,两种斜线前缀和如下图。
由此我们知道这个DP是O(mn^2)的。这种思路对于这道题来说不够优。我们需要优化。
整理一下DP方程。
dp[i] = \max \{dp[i - t] - g[i][s - t - 1] - c[s - t]\} + g[i][s - 1]
我们发现max标记里面的这个值其实可以单调队列处理,因为枚举的t有一个范围1 \leq t \leq p。设一个 h[i][j] = dp[i] - g[i][j - 1] - c[j] ,用h代换方程中的max里面的部分,单调队列维护的就是这个h。对于h的每一个j创建单调队列,在更新i的同时更新单调队列,这样就可以达到降低时间复杂度的目的。转移变为O(n)。
这里的思路去发现依赖关系和最值转移关系。
感觉dp数组都可以拿掉了,因为最后dp出来的值都是要插入单调队列里面的。可以稍稍优化空间常数。
初始值要设成买一个机器人的开销。以及我代码中的deque可以全换成手写双端队列,STL比较慢。
// Code by KSkun, 2018/2
#include <cstdio>
#include <cstring>
#include <deque>
#include <utility>
typedef std::pair<int, int> PI;
std::deque<PI> que[1005];
int n, m, p, sum[1005][1005], cost[1005], dp[1005], v;
inline int minus(int a, int b) { // return a - b
return ((a - b) % n + n) % n;
}
int main() {
scanf("%d%d%d", &n, &m, &p);
for(int i = 0; i < n; i++) {
for(int j = 1; j <= m; j++) {
scanf("%d", &sum[i][j]);
}
}
for(int i = 0; i < n; i++) {
scanf("%d", &cost[i]);
}
// 处理对角线前缀和
for(int i = 2; i <= m; i++) {
for(int j = 0; j < n; j++) {
sum[j][i] += sum[minus(j, 1)][i - 1];
}
}
// 设置初值表示开始一定要买一个机器人
for(int i = 0; i < n; i++) {
que[minus(i, -1)].push_back(std::make_pair(-cost[i], 0));
}
memset(dp, 0xc0, sizeof dp);
for(int i = 1; i <= m; i++) {
for(int j = 0; j < n; j++) {
dp[i] = std::max(dp[i], que[minus(j, i - 1)].front().first + sum[minus(j, 1)][i]);
}
for(int j = 0; j < n; j++) {
while(!que[minus(j, i - 1)].empty() && i - que[minus(j, i - 1)].front().second >= p) {
que[minus(j, i - 1)].pop_front();
}
v = dp[i] - sum[minus(j, 1)][i] - cost[j];
while(!que[minus(j, i - 1)].empty() && que[minus(j, i - 1)].back().first <= v) {
que[minus(j, i - 1)].pop_back();
}
que[minus(j, i - 1)].push_back(std::make_pair(v, i));
}
}
printf("%d", dp[m]);
return 0;
}
这周周考被基础算法虐翻了。%%%wxgdalao
wxg
赛题 #A: zcr搞破坏 | 贪心
赛题 #B: zcr爱吃鸡2 | 离散化,二分答案,枚举,模拟
赛题 #C: zcr解谜题 | DP,最大子矩阵
给出一个无向图,要求删掉图上的所有点。每一次删点的消耗是所有跟该点相连的所有未删除点的点权和。分别求最大权删法和次小权删法的消耗和。保证数据中无自环,且两点间最多有1条连边。
本题考察贪心思想。
试想对于边 (u, v) ,其中必然会有一个点会被加入最终答案。得到此性质后,考虑如何求最大权和最小权。对于求最大权的情况,我们需要把边中权值较大的点加入答案,而删除较小的点。
正确性的证明方面,我们应该考虑上面这个操作的完整形式。对于求最大权的情况,完整的操作应当是先对边以其中的较大权点的权值进行降序排序,再以该顺序删除每边中较大权的点。在这个过程中,大权点一定比小权点先被删除,因此能够保证求出答案的最优性。由于该操作要对每一条边进行,排序自然就没有必要,因此才有了上面的那种操作。
最小权的操作类比于最大权的操作。
关于求次小权,次小权一定存在于将最优删点顺序中相邻两点调换后的顺序的答案中,因此我们枚举调换的是哪两个点。考虑调换后对答案产生的影响,由于相邻两点的调换不会影响这两点之前、之后序列的单调性,因此只有两点间的连边会对答案造成影响。由于最多只可能有一条这样的边,我们检查是否有边,若无边则次小权等于最小权(无边对答案无影响),否则维护两点权值差的绝对值(即对答案产生的影响),次小权即是最小权加上前面影响的最小值。
总复杂度 O(nlogn) 。
// Code by KSkun, 2017/12
#include <cstdio>
#include <vector>
#include <algorithm>
struct io {
char buf[1 << 26], *s;
io() {
fread(s = buf, 1, 1 << 26, stdin);
}
inline int read() {
register int res = 0;
while(*s < '0' || *s > '9') s++;
while(*s >= '0' && *s <= '9') res = res * 10 + *s++ - '0';
return res;
}
} ip;
#define read ip.read
int n, m, kase, a[1000005], order[1000005], ut, vt;
long long resmax = 0, resmin = 0;
std::vector<int> vec[1000005];
inline bool cmp(int u, int v) {
return a[u] < a[v];
}
int main() {
n = read();
m = read();
kase = read();
for(int i = 1; i <= n; i++) {
a[i] = read();
if(kase == 2) order[i] = i;
}
for(int i = 0; i < m; i++) {
ut = read();
vt = read();
resmax += std::max(a[ut], a[vt]);
if(kase == 2) {
vec[ut].push_back(vt);
vec[vt].push_back(ut);
resmin += std::min(a[ut], a[vt]);
}
}
printf("%lld ", resmax);
if(kase == 1) {
return 0;
}
std::sort(order + 1, order + n + 1, cmp);
long long minn = 1e15;
for(int i = 1; i < n; i++) {
int u = order[i];
bool success = false;
for(int j = 0; j < vec[u].size(); j++) {
int v = vec[u][j];
if(v == order[i + 1]) {
success = true;
break;
}
}
minn = std::min(minn, 0ll + a[order[i + 1]] - a[u]);
if(!success) {
minn = 0;
break;
}
}
printf("%lld", resmin + minn);
return 0;
}
给出一些点,求能够包含其中C个点的最小正方形边长。
本题考察二分答案和枚举。
代码中,check()
函数用于枚举行,check1()
函数用于枚举列。
二分答案确定正方形边长的取值。然后枚举可能的正方形并且检验即可。
总复杂度O(n^2logn)。
// Code by KSkun, 2017/12
#include <cstdio>
#include <vector>
#include <algorithm>
#include <utility>
#include <vector>
struct io {
char buf[1 << 26], *s;
io() {
fread(s = buf, 1, 1 << 26, stdin);
}
inline int read() {
register int res = 0;
while(*s < '0' || *s > '9') s++;
while(*s >= '0' && *s <= '9') res = res * 10 + *s++ - '0';
return res;
}
} ip;
#define read ip.read
std::vector<std::pair<int, int> > points;
std::vector<int> tmp;
int c, n, xt, yt;
inline bool check1(int l, int r, int p) {
// 枚举列
if(r - l + 1 < c) return false;
tmp.clear();
for(int i = l; i <= r; i++) {
tmp.push_back(points[i].second);
}
sort(tmp.begin(), tmp.end());
for(int i = c - 1; i < tmp.size(); i++) {
if(tmp[i] - tmp[i - c + 1] <= p) return true;
}
return false;
}
inline bool check(int p) {
// 枚举行
int lastp = 0;
for(int i = 0; i < n; i++) {
if(points[i].first - points[lastp].first > p) {
//printf("i %d lastp %d\n", points[i].first, points[lastp].first);
if(check1(lastp, i - 1, p)) return true;
while(points[i].first - points[lastp].first > p) lastp++;
}
}
if(check1(lastp, n - 1, p)) return true;
return false;
}
int main() {
c = read();
n = read();
for(int i = 0; i < n; i++) {
xt = read();
yt = read();
points.push_back(std::make_pair(xt, yt));
}
std::sort(points.begin(), points.end());
int l = 0, r = 10005, mid;
while(r - l > 1) {
mid = (l + r) >> 1;
//printf("mid %d\n", mid);
if(check(mid)) r = mid;
else l = mid;
}
printf("%d", r + 1);
return 0;
}
本题中有一些暴力技巧降低复杂度,可以学习。
给出一个矩阵,求最大子矩形。其中,你有一次机会把任何数字改成给定值。
显然我们需要更改的只有可能是选中的矩形的最小值。
最小子矩形DP+预处理最小值。
总复杂度O(n^4)
考虑使用DP来递推“是否修改数字”这一状态。
dp[k][0/1]表示第k行未修改过(0)/修改过(1)数字的结果,状态转移方程如下
\begin{array}{l} dp[k][0] = max\{dp[k-1][0], 0\} + sum[k] \\ dp[k][1] = max\{dp[k-1][1], dp[k-1][0] + P - min[k]\} + sum[k] \end{array}
其中sum[k]代表当前选中的左右边界中第k行的和,min[k]代表边界中第k行的最小值。
答案在每个dp状态中,所以完成一次转移就要更新答案。
我们枚举矩形的左右边界,每一次枚举进行DP,即可得到总答案。
其实上述DP方法应该说是最大子矩形DP的一种变形,基本思路是一致的。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int n,m,p,a[305][305],sum[305],qz[305][305],minn[305],dp[305][2],ans;
int main()
{
cin>>n>>m>>p;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>a[i][j],qz[i][j]=qz[i][j-1]+a[i][j];
for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++)
minn[j]=a[j][i];
for(int j=i;j<=m;j++)
{
for(int k=1;k<=n;k++)
{
minn[k]=min(minn[k],a[k][j]);
sum[k]=qz[k][j]-qz[k][i-1];
}
dp[0][0]=0,dp[0][1]=-0x3f3f3f3f;
for(int k=1;k<=n;k++)
{
dp[k][0]=max(dp[k-1][0],0)+sum[k];
dp[k][1]=max(dp[k-1][1]+sum[k],max(dp[k-1][0],0)+sum[k]-minn[k]+p);
}
for(int k=1;k<n;k++) ans=max(ans,max(dp[k][0],dp[k][1]));
if(i==1&&j==m)
{
ans=max(ans,dp[n][1]);
int cnt=0;
for(int k=n;k>1;k--)
cnt+=sum[k],ans=max(ans,cnt);
}
else ans=max(ans,max(dp[n][0],dp[n][1]));
}
}
cout<<ans<<endl;
return 0;
}
本题是最大子矩形的一个变种,简单DP,有一些思维量。写的时候才发现我连最大子矩形都忘完了,药丸。