洛谷 P1220 关路灯（贪心+区间dp）

这一道题我一直在想时间该怎么算。

看题解发现有个隐藏的贪心。

路径一定是左右扩展的，左右端点最多加+1（我竟然没发现！！）

这个性质非常重要！！

因此这道题用区间dp

f[i][j]表示关完i到j的路灯的消耗。

那么因为要算走的路程，那么还有一维表示当前人在左端点

还是右端点。

然后每次的消耗为当前走这一段的时间乘上这个时候还亮着的路灯

的总功率。

然后这个起点的意义就在于在起点的消耗为0，其他都为正无穷

#include<cstdio>

#include<cstring>

#include<algorithm>

#define REP(i, a, b) for(int i = (a); i < (b); i++)

#define _for(i, a, b) for(int i = (a); i <= (b); i++)

using namespace std;

const int MAXN = 1123;

int f[MAXN][MAXN][2], t[MAXN][MAXN];

int w[MAXN], a[MAXN], n, s;

int main()

{

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

	_for(i, 1, n) scanf("%d%d", &a[i], &w[i]);

	_for(i, 1, n)

		_for(j, i, n)

			t[i][j] = t[i][j-1] + w[j];

	int sum = t[1][n];

	_for(i, 1, n)

		_for(j, i, n)

			t[i][j] = sum - t[i][j];

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

	f[s][s][0] = f[s][s][1] = 0;

	_for(d, 2, n)

		_for(i, 1, n)

		{

			int j = i + d - 1;

			if(j > n) break;

			f[i][j][0] = min(f[i+1][j][0] + t[i+1][j] * (a[i+1]-a[i]), f[i+1][j][1] + t[i+1][j] * (a[j]-a[i]));

			f[i][j][1] = min(f[i][j-1][0] + t[i][j-1] * (a[j]-a[i]), f[i][j-1][1] + t[i][j-1] * (a[j]-a[j-1]));

		}

	printf("%d\n", min(f[1][n][0], f[1][n][1]));

	return 0;

}

巴特西

洛谷 P1220 关路灯（贪心+区间dp）

最新文章

热门文章

巴特西

洛谷 P1220 关路灯 （贪心+区间dp）

最新文章

热门文章

洛谷 P1220 关路灯（贪心+区间dp）