概要

四邊形不等式的核心在于縮小最優轉移的范圍

題目描述

傳送門

解析

這道題說是不等式，但其實也可以感性理解
（其實就是不想證明）
定義pl[i][k]:

i到n的村莊建造k座郵局時，第一座管轄的范圍是i-pl[i][k]

(也就是最優決策的轉移點）
那么不難發現：

當新加一座郵局時，pl的值只可能變小
i向后移動一位時，pl的值只可能變大

抽象一下就是：

pl[i]k]<=pl[i][k-1]
pl[i][k]>=pl[i-1][k]

這樣就縮小了轉移的范圍
達到了優化的目的
轉移時一直記錄最優轉移點pl即可

#include<cstdio> #include<cstring> #include<cmath> #include<algorithm> using namespace std; const int N=3050; #define ll long long int n,m,a[N]; ll dp[N][350];//i,k表示起點為i，終點為n ll mid[N][N]; int pl[N][N]; void solve() {for(int l=1;l<=n;l++) {mid[l][l]=0;for(int r=l+1;r<=n;r++) {mid[l][r]=mid[l][r-1]+a[r]-a[l+r>>1];}} } int main(){scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){scanf("%d",&a[i]);}solve();for(int i=1;i<=n;i++) dp[i][1]=mid[i][n],pl[i][1]=n;for(int k=2;k<=m;k++){for(int i=1;i<=n;i++){dp[i][k]=2e15;for(int p=pl[i-1][k];p<=pl[i][k-1];p++){if(dp[i][k]>mid[i][p]+dp[p+1][k-1]){dp[i][k]=mid[i][p]+dp[p+1][k-1];pl[i][k]=p;} // printf("p=%d mid=%lld dp2=%lld\n",p,mid[i][p],dp[p+1][k-1]);} // printf("p[%d][%d]=%d p[%d][%d]=%d pnow=%d k=%d i=%d dp=%lld\n\n", // i-1,k,pl[i-1][k],i,k-1,pl[i][k-1],pl[i][k],k,i,dp[i][k]);}}printf("%lld\n",dp[1][m]); }

總結

以上是生活随笔為你收集整理的邮局-[IOI2000]（四边形不等式）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。