暴力枚举凸多边形起点，dp[i][j][k]维护起点是i，终点是j，由k个点组成的凸多边形
转移方程：dp[i][j][p+1]=max(dp[i][j][p+1],dp[i][k][p]+s(i,k,j));
#include<stdio.h> #include<string.h> #include<algorithm> #include<math.h> using namespace std; #define maxn 205 int n,m; int x[maxn],y[maxn]; long long dp[maxn][maxn][maxn]; int s(int i,int j,int k){ return x[i]*y[j]+x[j]*y[k]+x[k]*y[i]-x[i]*y[k]-x[j]*y[i]-x[k]*y[j]; } int main() { scanf("%d%d",&n,&m); for(int i=0;i<n;i++) scanf("%d%d",&x[i],&y[i]); for(int i=0;i<n;i++) x[i+n]=x[i],y[i+n]=y[i]; memset(dp,-1,sizeof(dp)); for(int i=0;i<n;i++) dp[i][i][1]=0; long long ans=0; for(int i=0;i<n;i++) for(int j=i+1;j<i+n;j++) for(int p=0;p<m;p++) for(int k=i;k<j;k++) { if(dp[i][k][p]==-1) continue; dp[i][j][p+1]=max(dp[i][j][p+1],dp[i][k][p]+s(i,k,j)); if(p+1==m) ans=max(ans,dp[i][j][p+1]); } printf("%lld",ans/2); if(ans%2==1) printf(".50\n"); else printf(".00\n"); }