洛谷1220（区间dp）

要点

处于什么位置的题常用一个套路就是搞完\([l,r]\)以后处于0（l）或1（r）的状态，即\(dp[i][j][0/1]\)。
对于此题dp意义为已经搞完\([l,r]\)的时最小的已耗电能，转移：以在\(i\)处为例，只会是\(i+1\)处直走过来或者\(j\)处掉头过来两种。写就很好写了。

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

const int maxn = 55;

int n, c;

int loc[maxn], W[maxn], sum[maxn];

int dp[maxn][maxn][2];

int calc(int x, int y, int l, int r) {

	return (loc[y] - loc[x]) * (sum[n] - sum[r] + sum[l - 1]);

}

int main() {

	scanf("%d %d", &n, &c);

	for (int i = 1; i <= n; i++) {

		scanf("%d %d", &loc[i], &W[i]);

		sum[i] = sum[i - 1] + W[i];

	}

	memset(dp, 0x3f, sizeof dp);

	dp[c][c][0] = dp[c][c][1] = 0;

	for (int i = c; i; --i) {

		for (int j = c; j <= n; j++) {

			if (i == c && j == c)	continue;

			dp[i][j][0] = min(dp[i + 1][j][0] + calc(i, i + 1, i + 1, j), dp[i + 1][j][1] + calc(i, j, i + 1, j));

			dp[i][j][1] = min(dp[i][j - 1][0] + calc(i, j, i, j - 1), dp[i][j - 1][1] + calc(j - 1, j, i, j - 1));

		}

	}

	return !printf("%d\n", min(dp[1][n][0], dp[1][n][1]));

}

巴特西

洛谷1220（区间dp）

要点

最新文章

热门文章