华电北风吹 天津大学认知计算与应用重点实验室 2016-08-14
题目链接： http://hihocoder.com/problemset/problem/1360
题目分析： 动态规划，思路参考Floyd解决所有节点对的最短路径类型的动态规划。
参考代码：
#include <iostream> #include <string.h> #include <algorithm> #include <iomanip> using namespace std; #define Length 105 struct 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; }