# 四边形不等式优化

2021-07-20 22:25:06 水沐银橙

Va10003 - Cutting Sticks

#### f[i][j]=min{f[i][k]+f[k+1][j]+a[j]-a[i-1]}

a[i]是前i段木棍的前缀和，实际上就是分割点

```#include<cstdio>
#include<cstring>
#include<iostream>

using namespace std;

const int N=55;
int pre[N],nxt[N];
int a[N],n,L;
int f[N][N];

int main()
{
while (scanf("%d",&L)!=EOF&&L)
{
scanf("%d",&n);
for (int i=1;i<=n;i++) scanf("%d",&a[i]);
a[n+1]=L;
int i,j,k;

memset(f,0x33,sizeof(f));
for (i=1;i<=n+1;i++) f[i][i]=0;
for (i=n;i>=1;i--)
for (j=i+1;j<=n+1;j++)
for (k=i;k<j;k++)
f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+a[j]-a[i-1]);

printf("The minimum cutting is ");
printf("%d.\n",f[1][n+1]);
}
return 0;
}```

## 四边形不等式

#### 称此式为四边形不等式

（可以形象理解为两个交错区间的w的和不超过小区间与大区间的w的和）

d(i)=min{d(j)+w(j+1,i) | j < i}

（可以形象理解为如果小区间包含于大区间中，那么小区间的w值不超过大区间的w值）

#### d(i,j)=min{d(i,k)+d(k+1,j)}+w(i,j) (s(i,j-1)≤k≤s(i+1,j))（min也可以改为max）

tip

```//这里写代码片
#include <cstdio>
#include <cstring>

const int N=55;
int s[N][N],f[N][N],a[N],n,L;

int main()
{
while (scanf("%d",&L)!=EOF&&L)
{
scanf("%d",&n);
for (int i=1;i<=n;i++) scanf("%d",&a[i]);
a[n+1]=L;
n++;

int i,j,k;
memset(f,0x33,sizeof(f));
for (i=1;i<=n;i++)
f[i][i]=0,s[i][i+1]=i;
for (i=1;i<=n;i++)
f[i][i+1]=a[i+1]-a[i-1];

for (i=n-2;i>=1;i--)
for (j=i+1;j<=n;j++)
for (k=s[i][j-1];k<=s[i+1][j];k++)
if (f[i][j]>f[i][k]+f[k+1][j]+a[j]-a[i-1])
{
f[i][j]=f[i][k]+f[k+1][j]+a[j]-a[i-1];
s[i][j]=k;
}

printf("The minimum cutting is ");
printf("%d.\n",f[1][n]);
}
return 0;
}```

https://blog.51cto.com/u_12136715/2954492