区间DP POJ1160

传送门
大佬题解

确定状态转移方程是很重要的
dp[i][j] 表示前i个村庄有几个邮局时的最优解
cost(i,j)表示 第i个到第j个村庄有一个邮局的时候的最优解
核心是要想到 如果有奇数个村庄 邮局应该建立在正中间
偶数个村庄的时候建立在中间的那两个村庄都一样

//MADE BY Y_is_sunshine;
//#include <bits/stdc++.h>
//#include <memory.h>
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <cstdio>
#include <vector>
#include <string>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>

#define INF 0x3f3f3f3f
#define MAXN 305
const int mod = 1e9 + 7;

using namespace std;

int N, M;
int dp[MAXN][MAXN];
int d[MAXN];

int cost(int x, int y) {
	int sum = 0;
	if (x == y)
		return 0;
	/*int mid = y - x >> 1; for (int i = 0; i < mid + 1; i++) { //只有一个邮局的时候 奇数建在中间 偶数的话两边都一样 sum += d[y - 1] - d[x + i]; } return sum;*/
	if ((y - x) & 1) {
		for (int i = 0; i <= (y - x) >> 1; i++)
			sum += d[y - i] - d[x + i];
		return sum;
	}
	for (int i = 0; i < ((y - x) >> 1) + 1; i++)
		sum += d[y - i] - d[x + i];
	return sum;
}


int main()
{

	freopen("data.txt", "r", stdin);

	cin >> N >> M;

	memset(dp, 0x3f, sizeof(dp));

	for (int i = 1; i <= N; i++) {
		scanf("%d", &d[i]);
		dp[i][1] = 0;
		for (int j = 1; j < i / 2 + 1; j++) { //只有一个邮局的时候 奇数建在中间 偶数的话两边都一样
			dp[i][1] += d[i - j + 1] - d[j];
		}
	}

	for (int k = 2; k <= M; k++) {			//枚举邮局数量
		dp[k][k] = 0;
		for (int i = k + 1; i <= N; i++) {
			for (int j = k; j <= i; j++) {
				dp[i][k] = min(dp[i][k], dp[j - 1][k - 1] + cost(j, i));
			}
		}
	}

	cout << dp[N][M] << endl;

	freopen("CON", "r", stdin);
	system("pause");
	return 0;
}