【DP】HDOJ 3480 Division

傾きDP。参照http://www.cnblogs.com/ka200812/archive/2012/08/03/2621345.html

#include <iostream>
#include <queue> 
#include <stack> 
#include <map> 
#include <set> 
#include <bitset> 
#include <cstdio> 
#include <algorithm> 
#include <cstring> 
#include <climits>
#include <cstdlib>
#include <cmath>
#include <time.h>
#define maxn 1005
#define maxm 300006
#define eps 1e-10
#define mod 1315423911
#define INF 1e9
#define lowbit(x) (x&(-x))
#define mp make_pair
#define ls o<<1
#define rs o<<1 | 1
#define lson o<<1, L, mid 
#define rson o<<1 | 1, mid+1, R 
typedef long long LL;
typedef unsigned long long ULL;
//typedef int LL;
using namespace std;

int n, m;
int a[10005];

void read(void)
{
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
}

int cmp(int a, int b)
{
	return a < b;
}

int dp[5005][10005];
int q[10005];

bool check1(int aa, int bb, int cc, int now)
{
	int y1 = dp[now][aa] + a[aa+1] * a[aa+1];
	int y2 = dp[now][bb] + a[bb+1] * a[bb+1];
	int y3 = dp[now][cc] + a[cc+1] * a[cc+1];
	int x1 = 2 * a[aa+1];
	int x2 = 2 * a[bb+1];
	int x3 = 2 * a[cc+1];
	return (y3 - y2) * (x2 - x1) <= (y2 - y1) * (x3 - x2);
}

bool check2(int aa, int bb, int now, int res)
{
	int y1 = dp[now][aa] + a[aa+1] * a[aa+1];
	int y2 = dp[now][bb] + a[bb+1] * a[bb+1];
	int x1 = 2 * a[aa+1];
	int x2 = 2 * a[bb+1];
	return (y2 - y1) <= (x2 - x1) * res;
}

void work(void)
{
	sort(a+1, a+n+1, cmp);
	for(int i = 1; i <= n; i++) dp[1][i] = (a[i] - a[1]) * (a[i] - a[1]);
	for(int i = 2; i <= m; i++) {
		int f = 0, t = 0;
		dp[i][1] = 0;
		for(int j = 1; j < n; j++) {
			while(t - f > 1 && check1(q[t-2], q[t-1], j, i-1)) t--;
			q[t++] = j;
			while(t - f > 1 && check2(q[f], q[f+1], i-1, a[j + 1])) f++;
			dp[i][j+1] = dp[i-1][q[f]] + (a[j+1] - a[q[f] + 1]) * (a[j+1] - a[q[f] + 1]);
		}
	}
	printf("%d
", dp[m][n]);
}

int main(void)
{
	int _, __;
	while(scanf("%d", &_)!=EOF) {
		__ = 0;
		while(_--) {
			read();
			printf("Case %d: ", ++__);
			work();
		}
	}
	
	return 0;
}