codeforces1117D
题目链接:http://codeforces.com/contest/1140/problem/D
题意:
就是告述你一个n多边形,顶点从1到n编号,让你把这个多边形分成三角形(个数不限, 保证所有三角形不相交,并且和为n边形的的面积即可)。求这些三角形的定点编号的乘积的和的最小值。
刚开始看见是D题,还以为会很难,直到我把代码写出来,看着就几行代码,都不太敢交,可没想居然几行代码就AC了。
思路:
要使三个定点的乘积尽量小,很朴素的想法就是让这三个顶点尽量小,于是我们考虑以1作为所有三角形的一个公共顶点。以此来划分三角形。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define INF 0x3f3f3f3f
typedef pair<int, int>p;
const int maxn = 1000*100*3 + 10;
ll n,k,a[maxn],b[maxn];
int main() {
ios::sync_with_stdio(false);
cin >> n;
int ans = 0;
for (int i = 3; i <= n; i++) {
ans += i * (i - 1);
}
cout << ans << endl;
return 0;
}