pku1294 极角序应用 at GCCFeli.cn

pku1294 极角序应用

评论17次阅读2008.08.25 11:14; 作者：Felicia　

这个题跟 pku1259 The Picnic 有些类似。具体做法是将除原点外所有点在全平面内极角排序，然后DP：
枚举起点`i`，设`f[j][k]`表示用`k`根橡皮筋圈住`i..j`的最小面积，可以转移到`f[j'][k + 1]`。
这样DP的时间复杂度是`O(bn^3)`。我一开始写的版本超时了，后来优化常数过的，很慢。如果有更好的做法请告诉我@_@

下面是我的主要代码

int b, n;

const int maxn = 110;

vector <point> p;

int f[maxn][maxn];
int conv[maxn][maxn];

int ed[maxn];

int calc() {
   int ret = maxint;
   polar_angle_sort_full(p);

   int n = SZ(p);

   for (int i = 0; i < n; i++)
   for (int j = 0; j < n; j++)
   conv[i][j] = maxint;

   for (int i = 0; i < n; i++) {
   int j;
   for (j = (i + 1) % n; sgn(cross(p[i], p[j])) > 0; j = (j + 1) % n);
   ed[i] = j;
   }

   for (int i = 0; i < n; i++) {
   for (int j = (i + 1) % n; j != ed[i]; j = (j + 1) % n) {
   point tp[110];
   int np = 0;
   tp[np++] = point(0, 0);
   for (int k = i; k != j; k = (k + 1) % n)
   tp[np++] = p[k];
   tp[np++] = p[j];
   conv[i][j] = area_poly(convex_hull(tp, np));
   }
   }
   for (int i = 0; i < n; i++) {
   for (int j = 0; j < n; j++)
   for (int k = 0; k <= b; k++)
   f[j][k] = maxint;
   for (int j = (i + 1) % n; j != ed[i]; j = (j + 1) % n)
   f[j][1] = conv[i][j];
   for (int k = 1; k < b; k++) {
   for (int j = (i + 1) % n; j != i; j = (j + 1) % n) if (f[j][k] != maxint) {
   int j1 = (j + 1) % n;
   for (int q = (j + 2) % n; q != ed[j1] && q != i; q = (q + 1) % n) {
   get_min(f[q][k + 1], f[j][k] + conv[j1][q]);
   }
   }
   }
   get_min(ret, f[(i + n - 1) % n][b]);
   }
   return ret;
}

标签云: 动态规划, 计算几何 | 日志分类: 动态规划, 计算几何

如需转载烦请添加以下信息: 本文转自Felicia@GCCFeli.cn

评论 (0)
引用通告 (0)
发表评论引用通告

暂无评论.

暂无引用通告

发表回复