题面在这里
题意
英国军官劳伦斯带领一群阿拉伯国民对奥斯曼帝国进行游击队袭击。
他的主要目标是铁路。
整条铁路有(n)个仓库,每个仓库都有一个战略价值(x_i)。
对于每条完整的铁路([l,r])，其战略价值为铁路上两两仓库的战略价值之和,即((sum_{k=l}^{r}x[k])^2-sum_{k=l}^{r}x[k]^2)
现在劳伦斯可以摧毁(m)条铁路,求他摧毁铁路后所有(m+1)段铁路战略价值之和的最小值
数据范围
sol
设(f[i][j])为将前(i)个仓库分成(j)段所需的最小代价,答案存在(f[i][m+1])里
那么(O(n^3))的方程显然:
其中(w[i,j]=frac{1}{2}((sum_{k=i}^{k=j}x[i])^2-sum_{k=i}^{k=j}x[i]^2))
容易发现(w[i,j])满足区间包含关系单调
对于(ile i'le jle j'),可以发现
( herefore w[i,j]+w[i',j']le w[i,j']+w[i',j]，)即(w[i,j])满足平行四边形不等式
然后我们需要证明决策单调;
令(s[i][j]=max){(p)|(f[i][j]=f[p][j-1]+w[p+1][i])},即最大转移点
打个表可以发现(s[i][j]le s[i+1][j])，证明这个就相当于把复杂度变成了(O(n^2))
其实我们根据这个不等式写一发交上去就可以AC了...
其实本人在A掉这道题之前也并没有证明转移点的单调性...
那么我们现在需要证明:(s[i][j]le s[i+1][j])
设(p_1=max){(p)|(f[i][j]=f[p][j-1]+w[p+1][i])},
那么原式即(forall p_2le p_1,)
(f[p_2][j-1]+w[p_2+1][i+1]ge f[p_1][j-1]+w[p_2+1][i+1])
由(p_1)的性质有(f[p_2][j-1]+w[p_2+1][i]ge f[p_1][j-1]+w[p_2+1][i])
那么只要证
即可(对这个式子有两行)
要证上式并不难,化简后会发现只要证
对于(p_2le p_1le i<i+1)，上式明显就是四边形不等式
综上所述，命题得证
本人证明不是很好...如有疏漏欢迎指出
代码
#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<iomanip>
#include<cstring>
#include<complex>
#include<vector>
#include<cstdio>
#include<string>
#include<bitset>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<set>
#define mp make_pair
#define pb push_back
#define RG register
#define il inline
using namespace std;
typedef unsigned long long ull;
typedef vector<int>VI;
typedef long long ll;
typedef double dd;
const dd eps=1e-10;
const int mod=1e8;
const int N=1010;
il ll read(){
RG ll data=0,w=1;RG char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
if(ch=='-')w=-1,ch=getchar();
while(ch<='9'&&ch>='0')data=data*10+ch-48,ch=getchar();
return data*w;
}
il void file(){
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
}
int n,m,a[N],d[N],w[N][N],f[N][N],s[N][N];
int main()
{
while(2333){
n=read();m=read();
if(!n&&!m)break;
for(RG int i=1;i<=n;i++){
d[i]=a[i]=read();d[i]*=a[i];
a[i]+=a[i-1];d[i]+=d[i-1];
}
for(RG int i=1;i<=n;i++)
for(RG int j=i+1;j<=n;j++){
w[i][j]=(a[j]-a[i-1])*(a[j]-a[i-1])-(d[j]-d[i-1]);
w[i][j]/=2;
}
memset(f,63,sizeof(f));
for(RG int i=1;i<=n;i++){
f[i][0]=w[1][i];
for(RG int j=1;j<=min(i-1,m);j++){
for(RG int k=s[i-1][j];k<=i-1;k++){
if(f[i][j]>=f[k][j-1]+w[k+1][i]){
f[i][j]=f[k][j-1]+w[k+1][i];
s[i][j]=k;
}
}
}
}
printf("%d
",f[n][m]);
}
return 0;
}