华电北风吹
天津大学认知计算与应用重点实验室
2016-08-14

题目链接：
http://hihocoder.com/problemset/problem/1360

题目分析：
动态规划，思路参考Floyd解决所有节点对的最短路径类型的动态规划。

参考代码：

#include <iostream>
#include <string.h>
#include <algorithm>
#include <iomanip>
using namespace std;#define Length 105struct Point
{int x, y;
};
int N, M;
Point point[Length];
double tringleSize[Length][Length][Length], state[Length][Length][Length];double CalculateTringle(int i, int j, int k)
{return 0.5*(point[i].x * point[j].y + point[j].x * point[k].y + point[k].x * point[i].y - point[i].x * point[k].y - point[j].x * point[i].y - point[k].x * point[j].y);
}int main()
{cin >> N >> M;for (int i = 0; i < N; i++){cin >> point[i].x >> point[i].y;}for (int i = 0; i < N; i++){for (int j = 0; j < N; j++){for (int k = 0; k < N; k++){tringleSize[i][j][k] = abs(CalculateTringle(i, j, k));}}}memset(state, 0, sizeof(state));for (int k = 3; k <= M; k++){for (int i = 0; i < N; i++){for (int j = i + 1; j != i; j = (j + 1) % N){for (int u = i + 1; u != j; u = (u + 1) % N){state[i][j][k] = max(state[i][j][k], state[i][u][k - 1] + tringleSize[u][j][i]);}}}}double result = 0;for (int i = 0; i < N; i++){for (int j = 0; j < N; j++){result = max(result, state[i][j][M]);}}cout << fixed << setprecision(2) << result << endl;return 0;
}