潍坊网站建设SEO优化,wordpress页面的设置,推荐软件分类,wordpress付费文章插件昨天晚上写的时候看错题了#xff0c;以为并不是交替走#xff0c;最后没时间了读了一遍题目发现是交替走#xff0c;然后就秒了但是已经没时间写了。
其实昨天并不想写#xff0c;不过看了下D题发现是个数学题#xff0c;虽然我数学题非常渣渣#xff0c;但是拿起笔就推…昨天晚上写的时候看错题了以为并不是交替走最后没时间了读了一遍题目发现是交替走然后就秒了但是已经没时间写了。
其实昨天并不想写不过看了下D题发现是个数学题虽然我数学题非常渣渣但是拿起笔就推了推式子发现可做写完代码后第一次交RE数组开小了第二次交Wa很奇怪最后发现预处理应该是2×1062×10^62×106非常蛋疼~ C. Minimum Grid Path
预处理前缀和以及前缀最小值由于是交替走只有两种情况两个方向都走kkk次或者一个方向走k1k1k1次一个方向走kkk次枚举kkk计算即可。
#includecstring
#includeiostream
#includealgorithm
using namespace std;
using lllong long;
constexpr int N200010;
int n;
ll c[N];
ll a[N],b[N];
ll sa[N],sb[N];
ll ma[N],mb[N];
int cnta,cntb;
ll calc(int k)
{ll res1e18;resmin(res,sa[k]ma[k]*(n-k)sb[k]mb[k]*(n-k));if(k1cnta) resmin(res,sa[k1]ma[k1]*(n-k-1)sb[k]mb[k]*(n-k));return res;
}
int main()
{ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);int T1;cinT;while(T--){cinn;for(int i1;in;i) cinc[i];cntacntb0;for(int i1;in;i2) a[cnta]c[i];for(int i2;in;i2) b[cntb]c[i];sa[0]sb[0]0;for(int i1;icnta;i) sa[i]sa[i-1]a[i];for(int i1;icntb;i) sb[i]sb[i-1]b[i];ma[0]mb[0]1e18;for(int i1;icnta;i) ma[i]min(ma[i-1],a[i]);for(int i1;icntb;i) mb[i]min(mb[i-1],b[i]);ll res1e18;for(int i1;imin(cnta,cntb);i) resmin(res,calc(i));coutres\n;}return 0;
}
