题目传送门

思路

曾经一致认为数据错了，因为 xyd 的代码过不去。

考虑一个问题——如何记录已知信息。容易发现可以将多边形转化为一个长度为 $2n$ 的序列，每个两个元素存一条边的长度和度数。已知的信息一定是该序列的一个子串，数量是 $O(n^2)$ 级的。设这个序列为 $s$，长度为 $m$。

考虑 dp，设 $dp_{l,r,p,0/1}$ 表示已知的信息为 $s_{l\cdots r}$，且在已知信息串的第 $p$ 个开始，最终停在了 $l$ 或者 $r$ 的最小距离。随之而来的，我们遇到一个问题——无法唯一出信息串。即可能存在 $i,j$ 使得 $s_{l_i\cdots r_i}=s_{l_j\cdots r_j}$，显然这是无法区分的。不妨假设 $l_i<l_j$，我们得到 $dp_{l_i,r_i}$，再将其他的 $dp_{l_j,r_j}$ 转移到 $dp_{l_i,r_i}$ 上面去。那么，$(l_i,r_i)$ 就是这些无法分辨串的“代表”。

考虑转移，不难发现决策方式只有 $2$ 种，即向左或向右走。对于每个 $(l,r)$ 的信息串，我们记录 $ll_{l,r},rr_{l,r}$ 表示向左或向右拓展一格可能到达的代表串。那么两种决策代价就是 $\max dp_{ll}$ 和 $\max dp_{rr}$。有转移 $dp_{l,r}=\min\{\max dp_{ll},\max dp_{rr}\}$。

答案计算，$\text{answer}=\displaystyle\max_i dp_{i,i,1,0/1}$。时间复杂度 $O(n^3)$。

代码

真的调的很辛苦，不要直接抄啊！

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7,base=31;
const int inf=0x3f3f3f3f;
const int N=405;
int n,m,id[N],dis[N],prf[N],str[N],pos[N],fir[N][N],dp[N][N][N][2],ans;
vector <int> ll[N][N],rr[N][N];
struct node{int x,y;}a[N];
int flag(int x){return x>0?-1:-2;}
int pre(int x){return x==1?n:x-1;}
int nxt(int x){return x==n?1:x+1;}
int Dist(int i,int j,int k){return (a[j].x-a[i].x)*(a[k].y-a[i].y)-(a[j].y-a[i].y)*(a[k].x-a[i].x);}
int dist(int i,int j){return abs(a[i].x-a[j].x)+abs(a[i].y-a[j].y);}
signed main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d%d",&a[i].x,&a[i].y);
	for(int i=1;i<=n;i++){
		int p1=pre(i),p2=nxt(i);
		str[++m]=flag(Dist(i,p1,p2));
		str[++m]=dist(i,p2);
		id[i]=m-1,pos[m-1]=i;
		prf[i+1]+=str[m]; 
		prf[i]+=prf[i-1];
	}
	str[1]=str[++m]=0,id[n+1]=m,pos[m]=n+1,prf[n+1]+=prf[n];
	for(int i=1;i<=n;i++) dis[i]=min(prf[i],prf[n+1]-prf[i]);
	for(int len=1;len<=m;len++){
		for(int l=1;l+len-1<=m;l++){
			int r=l+len-1;
			for(int i=1;i<l;i++){
				if(str[r]!=str[i+len-1]) continue;
				if(fir[l][r-1]!=fir[i][i+len-2]) continue;
				fir[l][r]=i;break;
			}
			if(!fir[l][r]) fir[l][r]=l;
		}
	}
	for(int len=3;len<=m;len+=2){
		for(int l=1;l+len-1<=m;l+=2){
			int r=l+len-1;
			if(fir[l][r]!=l) continue;
			ll[pos[fir[l+2][r]]][pos[fir[l+2][r]+len-3]].push_back(pos[l]);
			rr[pos[fir[l][r-2]]][pos[fir[l][r-2]+len-3]].push_back(pos[r]);
		}
	}
	for(int len=n+1;len>=1;len--){
		for(int l=1;l+len-1<=n+1;l++){
			int r=l+len-1;
			if(fir[id[l]][id[r]]!=id[l]) continue;
			int now=prf[r]-prf[l];
			for(int s=1;s<=len;s++){
				for(int x=0;x<=1;x++){
					if(l==1||r==n+1){dp[l][r][s][x]=-dis[l+s-1];continue;}
					int lc=-inf,rc=-inf;
					for(int p:ll[l][r]) lc=max(lc,dp[p][p+len][s+1][0]+str[id[p]+1]);
					for(int p:rr[l][r]) rc=max(rc,dp[p-len][p][s][1]+str[id[p]-1]);
					if(x) lc+=now;
					else rc+=now;
					dp[l][r][s][x]=min(lc,rc);
					if(len==1) ans=max(ans,dp[l][r][s][x]);
				}
			}
		}
	}
	printf("%d",ans);
	return 0;
}

撒花！

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

#define MAXN 210
#define INF 0x3FFFFFFF

int opt[MAXN];
int psum[MAXN];
int canon[MAXN*2][MAXN*2];
vector<int> lparents[MAXN][MAXN];
vector<int> rparents[MAXN][MAXN];

int dp[MAXN][MAXN][MAXN][2];

int main() {
  int N; cin >> N;
  vector<pair<long long, long long> > A(N);
  for (int i = 0; i < N; i++) {
    cin >> A[i].first >> A[i].second;
  }

  /* Create the underlying string from the polygon.  Represent the exit as
   * 0.  Represent clockwise turns as -1, counter clockwise as -2.  Represent
   * lengths by their length.
   */
  vector<int> S(1, 0);
  for (int i = 0; i < N; i++) {
    int j = (i + 1) % N;
    int k = (i + 2) % N;
    S.push_back(abs(A[i].first - A[j].first) +
                abs(A[i].second - A[j].second));

    /* Use a cross product to determine which way the polygon turned. */
    if ((A[i].first - A[j].first) * (A[k].second - A[j].second) -
        (A[k].first - A[j].first) * (A[i].second - A[j].second) > 0) {
      S.push_back(-1);
    } else {
      S.push_back(-2);
    }
  }
  S.back() = 0;

  /* Compute the lights-on cost for each corner. */
  for (int i = 0; i < N; i++) {
    psum[i + 1] = opt[i + 1] = opt[i] + S[2 * i + 1];
  }
  opt[N] = 0;
  for (int i = N - 1; i >= 0; i--) {
    opt[i] = min(opt[i], opt[i + 1] + S[2 * i + 1]);
  }

  /* Compute j = canon[i][ln] to be the first j s.t. S[j:j+ln-1] = S[i:i+ln-1].
     The canonical starting position of the string S[i:i+ln-1].
   */
  for (int ln = 1; ln <= S.size(); ln++) {
    for (int i = 0; i + ln <= S.size(); i++) {
      for (int& j = canon[i][ln]; j < i; j++) {
        /* If ln - 1 matches and the last character matches... */
        if (canon[j][ln - 1] == canon[i][ln - 1] &&
            S[j + ln - 1] == S[i + ln - 1]) {
          break;
        }
      }
    }
  }
  
  /* Pre-compute the state transitions; how to extend left and right for each
   * possible string. */
  for (int i = 0; i < S.size(); i += 2) {
    for (int ln = 3; i + ln <= S.size(); ln += 2) {
      if (i != canon[i][ln]) {
        continue;
      }
      lparents[canon[i + 2][ln - 2] / 2][ln / 2].push_back(i / 2);
      rparents[canon[i][ln - 2] / 2][ln / 2].push_back(i / 2);
    }
  }

  int result = 0;
  for (int ln = N; ln >= 1; ln--) {
    for (int i = 0; i + ln <= N + 1; i++) {
      if (canon[2 * i][2 * ln - 1] != 2 * i) {
        /* Non-canonical string, skip. */
        continue;
      }

      int dist_across = psum[i + ln - 1] - psum[i];
      for (int strt = 0; strt < ln; strt++) {
        for (int side = 0; side < 2; side++) {
          if (i == 0 || i + ln == N + 1) {
            /* We're at the exit. */
            dp[i][ln][strt][side] = -opt[i + strt];
            continue;
          }

          /* Compute the worst case cost for left and right. */
          int lft_cst = -INF;
          for (int j : lparents[i][ln]) {
            lft_cst = max(lft_cst, S[2 * j + 1] + dp[j][ln + 1][strt + 1][0]);
          }

          int rht_cst = -INF;
          for (int j : rparents[i][ln]) {
            rht_cst = max(rht_cst,
                          S[2 * (j + ln) - 1] + dp[j][ln + 1][strt][1]);
          }

          /* Add in the cost for crossing the string if we choose to extend the
           * far side of the string. */
          (side ? lft_cst : rht_cst) += dist_across;

          /* Result is just the min of these two choices. */
          dp[i][ln][strt][side] = min(lft_cst, rht_cst);

          /* Update the result if this is a 1 length string. */
          if (ln == 1) {
            result = max(result, dp[i][ln][strt][side]);
          }
        }
      }
    }
  }
  cout << result << endl;
  
  return 0;
}