題目連結:hdu 5473 There was a kingdom
解題思路
選取的點一定在凸包上,是以對點集做凸包,如果凸包的點個數小于等于K,面積可以取到最大值。否則,枚舉起點,做動态規劃。dp[i][j]表示到第i個點選取了j個點的最優解。這樣的複雜度為 o(n2k) ,算上枚舉起點總得複雜度為 o(n3k) 。但是,我們選取的是k個點,如果有枚舉到一次的起點在這k個點上,即可以命中最優答案,是以枚舉的次數不用很多就可以将命中機率趨近與1。
代碼
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long ll;
struct Point {
ll x, y;
Point(ll x = , ll y = ): x(x), y(y) {}
void read() { scanf("%lld%lld", &x, &y); }
bool operator < (const Point& u) const { return x < u.x || (x == u.x && y < u.y); }
bool operator == (const Point& u) const { return !(*this < u) && !(u < *this); }
bool operator != (const Point& u) const { return !(*this == u); }
bool operator > (const Point& u) const { return u < *this; }
bool operator <= (const Point& u) const { return *this < u || *this == u; }
bool operator >= (const Point& u) const { return *this > u || *this == u; }
Point operator + (const Point& u) { return Point(x + u.x, y + u.y); }
Point operator - (const Point& u) { return Point(x - u.x, y - u.y); }
Point operator * (const double u) { return Point(x * u, y * u); }
Point operator / (const double u) { return Point(x / u, y / u); }
ll operator ^ (const Point& u) { return x*u.y - y*u.x; }
};
typedef Point Vector;
ll Cross(Vector a, Vector b) { return a.x * b.y - a.y * b.x; }
ll getArea (Point* p, int n) {
ll ret = ;
for (int i = ; i < n-; i ++)
ret += Cross(p[i]-p[], p[i+]-p[]);
return ret < ? -ret : ret;
}
int getConvexHull (Point* p, int n, Point* ch) {
sort(p, p + n);
int m = ;
for (int i = ; i < n; i++) {
while (m > && Cross(ch[m-]-ch[m-], p[i]-ch[m-]) <= ) m--;
ch[m++] = p[i];
}
int k = m;
for (int i = n-; i >= ; i--) {
while (m > k && Cross(ch[m-]-ch[m-], p[i]-ch[m-]) <= ) m--;
ch[m++] = p[i];
}
if (n > ) m--;
return m;
}
const int maxn = ;
int N, K;
ll dp[maxn][maxn];
Point P[maxn], Q[maxn];
ll solve () {
ll allarea = getArea(P, N);
if (K >= N) return allarea;
ll ret = ;
bool vis[maxn];
memset(vis, , sizeof(vis));
int ti = min( * (N / K), N);
//int ti = min(10, N);
for (int t = ; t < ti; t++) {
int s = rand() % N;
while (vis[s]) s = rand() % N;
vis[s] = ;
memset(dp, , sizeof(dp));
dp[][] = allarea;
for (int i = ; i <= N; i++) {
int u = (i + s) % N;
ll sum = ;
for (int j = i-; j >= ; j--) {
int v = (j + s) % N;
int p = (v + ) % N;
ll tmp = ((P[p]-P[u])^(P[v]-P[u]));
if (tmp < ) tmp = -tmp;
sum += tmp;
for (int x = K; x > ; x--)
dp[i][x] = max(dp[i][x], dp[j][x-]-sum);
}
}
ret = max(ret, dp[N][K]);
}
return ret;
}
int main () {
int cas;
scanf("%d", &cas);
srand((int)time(NULL));
for (int kcas = ; kcas <= cas; kcas++) {
scanf("%d%d", &N, &K);
for (int i = ; i < N; i++) Q[i].read();
N = getConvexHull(Q, N, P);
printf("Case #%d: %lld\n", kcas, solve());
}
return ;
}