HDU - 3480-526互联

$HDU - 3480$（斜率优化与四边形不等式优化）

$name$	$time(ms)$	$mem(mb)$	$lenth$
四边形不等式优化	$2074$	$362.1$	$731$
斜率优化	$1669$	$166.4$	$1480$

斜率优化内存大有是二维数组，没改成一维的原因

1.斜率优化

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int INF = 2e9;
const LL LNF = 9e18;
const int mod = 1e9+7;
const int MAXM = 1e5+10;
const int MAXN = 1e4+10;

int val[MAXN], dp[MAXN][MAXN];
int q[MAXN], head, tail;
int ans[100001];

int up(int i, int k1, int k2){
    return (dp[i-1][k1] + val[k1+1]*val[k1+1])-(dp[i-1][k2] + val[k2+1]*val[k2+1]);
}

int down(int k1, int k2){
    return 2*(val[k1+1]-val[k2+1]);
}

int getDP(int i, int j, int k){
    return dp[i-1][k] + (val[j]-val[k+1])*(val[j]-val[k+1]);
}

int main()
{
    int n, m, T;
    cin >> T;
    for(int kase = 1; kase<=T; kase++)
    {
        cin >> n >> m;
        for(int i = 1; i<=n; i++)
            cin >> val[i];
        sort(val+1, val+1+n);
        for(int i = 1; i<=n; i++)
            dp[1][i] = (val[i]-val[1])*(val[i]-val[1]);
        for(int i = 2; i<=m; i++)
        {
            head = tail = 0;
            q[tail++] = i-1;
            for(int j = i; j<=n; j++)
            {
                while(head+1<tail && up(i,q[head+1],q[head])<down(q[head+1], q[head])*val[j]) head++;
                dp[i][j] = getDP(i,j,q[head]);

                while(head+1<tail && up(i,j,q[tail-1])*down(q[tail-1],q[tail-2])<=
                      up(i,q[tail-1],q[tail-2])*down(j,q[tail-1])) tail--;
                q[tail++] = j;
            }
        }
        ans [kase] = dp[m][n];
    }
	for(int i = 1 ; i <= T ; i++){
		cout << "Case " << i << ": " <<ans[i] <<endl; 
	}
	return 0;
}

其实也可以用滚动数组优化一维DP，但我不想，问就是懒（不想改）。

斜率优化的特点是：

1.一般是一维的，斜率优化用到单调队列（可以用数组代替），单调队列二维不好模拟

2.有乘积项，斜率优化的数学推导需要用到一个人尽皆知的数学公式: 完全平方公式。

给出一个基本形式：$ dp[i] = min (dp[i],A * dp[j] + i * j + c) $

$tips$ : $ i * j $ 只需要是 $i$ 与 $j$ 的乘积项。

知道了什么是斜率优化，剩下的只剩推式子，每一个都不一样，那就先扯一个式子过来（猜猜是那一道题的？提示：$HDU$）

现在有这么个式子来示范怎么推式子 ~~都学过数学吧？~~ ，它是怎么得到的你不用管，一般在题目中是没有优化的 $dp$ 式子。

$ dp[i] = min ( dp[i] , dp[j] + m + ( sum[i] - sum[j] ) ^ {2} ) $ (求的是最小值)

（这是共通的一步，将两个能推向状态 $i$ 的决策点代入式子经行比较）假设有两个决策点: $j$ , $k$ , 且 $k<j$ , $j$ 是较优解 (因为 $j$ 也可能被淘汰)，那么：

$ dp[j] + m + ( sum[i] - sum[j] ) ^ {2} <= dp[k] + ( sum[i] - sum[k] ) ^ {2} $

$ dp[j] + sum[i] ^ {2} - 2 * sum[i] * sum[j] + sum[j] ^ {2} <= dp[k] + sum[i] ^ {2} - 2 * sum[i] * sum[k] + sum[k] ^ {2} $

$ dp[j] + sum[j] ^ {2} - ( dp[k] + sum[k] ^ {2} ) <= 2 * sum[i] * ( sum[j] - sum[k] ) $

2.四边形不等式优化

代码：

#include<bits/stdc++.h>
using namespace std;
const int inf=1000000000;
int t;
int n,m;
int dp[5001][10001];
int pos[5001][10001];
int a[10001];

void ans(){
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	sort(a+1,a+1+n);
	for(int i=1;i<=n;i++){
		pos[0][i]=1;
	}
	dp[0][0]=0;
	for(int i=1;i<=m;i++){
		dp[i][i]=0;
		pos[i][i]=i;
		pos[i][n+1]=n;
		for(int j=n;j>i;j--){
			for(int k=pos[i-1][j];k<=pos[i][j+1];k++){
				if(dp[i][j]>dp[i-1][k-1]+(a[j]-a[k])*(a[j]-a[k])){
					dp[i][j]=dp[i-1][k-1]+(a[j]-a[k])*(a[j]-a[k]);
					pos[i][j]=k;
				}
			}
		}
	}
	return;
}

int main(){
	int now=0;
	cin>>t;
	while(t--){
		now++;
		cin>>n>>m;
		memset(dp,0x3f,sizeof(dp));
		ans();
		cout<<"Case "<<now<<": "<<dp[m][n]<<endl;
	}
	return 0;
}

比斜率优化短很多，但是不好证明 ~~证明不重要eee~~~

下面介绍一下四边形不等式优化:

对于形如以下的状态方程：
dp[i][j] = min ( dp[i][j] , dp[i][k-1] + dp[k][j] + cost[k][j] );

或dp[i][j]>dp[i][j-1] 且 dp[i-1][j]>dp[i][j]

( dp[i][k-1] , dp[k][j] 有时会合并成1项）

是具有单调性的：你可以暴力打表对拍：下面给出一组例子：