首页 > 代码库 > Codeforces 429D Tricky Function 近期点对
Codeforces 429D Tricky Function 近期点对
题目链接:点击打开链接
暴力出奇迹。
正解应该是近期点对。以i点为x轴,sum[i](前缀和)为y轴,求随意两点间的距离。
先来个科学的暴力代码:
#include<stdio.h> #include<string.h> #include<vector> #include<algorithm> #include<iostream> #include<queue> using namespace std; #define N 100050 #define ll __int64 ll a[N], sum[N]; ll n; int main(){ ll u, v, i, j, que; sum[0] = 0; while(~scanf("%I64d",&n)){ for(i=1;i<=n;i++)scanf("%I64d",&a[i]),sum[i] = sum[i-1]+a[i]; ll ans = a[2]*a[2]+1; for(i = 1; i <= n; i++){ if(i*i>=ans)break; ll tmp = ans; for(j = i+1; j<=n; j++){ tmp = min(tmp, (sum[j]-sum[j-i])*(sum[j]-sum[j-i])); } ans = min(ans, tmp+i*i); } printf("%I64d\n",ans); } return 0; }
Codeforces 429D Tricky Function 近期点对
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。