CF1555C 题解

 原文

作为直到最后才勉强通过的蒟蒻，在这里发篇题解记录一下我的想法。

悲伤了，卡点过水题

原题链接

题意解释

题目的意思，大概是这样的：

有一个 22 × mm 的矩阵。

Alice 和 Bob 都在矩阵上的 (1,1)(1,1) 处。 Alice 先出发，每到一个房间就会将这个房间所有的 coins 全部都拿走，她很聪明（她总是很聪明），会用最聪明的走法，使得在她拿走她经过路径上的所有 coins 之后，让 Bob 接下来走的时候拿的最大的 coins 总和最小。而 Bob 也非常的聪明（他也总是很聪明）,会在 Alice 走后,选取一条路径可以使得他在剩下的 coins 拿走最大的总和。

注意：每一次他们都只能往右和往下走一步。

输出在他们两个人都很聪明的情况下 Bob 最后的得分。

关键点

曾经有一位巨佬说过，做题，需要找到题目的关键点。

所以我们先来看一下，这道题目中的一线关键点：

• Alice 和 Bob 都很聪明 (这是重点，着重关注)
• 每一次他们都只能往右和往下走一步
• 一个 22 × mm 的矩阵

第一个关键点给我们带来的是，答案一定是最优解 （fake几句） 。
第二个关键点给我们的信息是一旦 Alice 和 Bob 下去以后，就不能上来了 。 第三个关键点提示我们，这其实是一道水题。

画图找解法

接下来我们采用画图的方式，找到答案.
绿色是 Alice 走的路径。

感谢@QueenSi的画图助力

我相信大家已经从图中发现了， Alice 从哪个位置下去就决定了她所走的路径，也就决定了 Bob 能得到的 coins 最大的总和。

由于 Bob 与 Alice 的路径限制条件一样，且矩阵高为 22，所以我们就会发现图中红色部分和蓝色部分就是出现 Bob 能得到 coins 最大的总和的唯一的两个区域。

那么一切就都已经出来了，接下来，附上代码，完事！

CODE

#include#define int long longusing namespace std;const int maxn=1e5+1e3;int T,m;int a[maxn],b[maxn],ans[maxn],sum1,sum2,answer;inline int read(){    int res=0,f=1;char c;    for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;    for(;isdigit(c);c=getchar()) res=(res<<1)+(res<<3)+(c^48);    return res*f;}signed main(){    T=read();    while(T--)    { memset(ans,0,sizeof ans); //初始化ans值  answer=0x3f3f3f3f,sum1=0,sum2=0;//将ans赋值为0x3f3f3f3f，方便后面取min //sum1记录在i位置下去时上方红色部分总和 //sum2记录在i位置下去时下方蓝色部分总和  m=read(); for(int i=1;i<=m;i++) a[i]=read(),sum1+=a[i];//提前处理好第一排总和  for(int i=1;i<=m;i++) {     b[i]=read();     sum1-=a[i];//由上面图可知，红色部分从i+1开始      ans[i]=max(sum1,sum2);//取蓝色部分和红色部分中的大值（Bob的聪明）      answer=min(ans[i],answer);//取所有蓝色部分和红色部分中的大值中的最小值（Alice的聪明）      sum2+=b[i];// 由上面图可知，蓝色部分到i-1结束  } printf("%lld\n",answer);//最后输出answer,完事     }    return 0;}