本文主要是介绍P1220 关路灯，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

感谢所有AC

传送门

经验

       当遇到动点的$dp$问题时，需要注意动点所在位置对状态转移的影响，如果有影响，可以适当考虑增加一个维度用来表示动点地位置状态。

思路

       由于老李关掉灯的时间忽略不计，因此老李所过之处一定是所有灯全灭，那么关灯就可以有两种选择，一种是沿着现在行进的方向继续关下一盏灯，另一种是掉头去关另一盏灯。可以用状态 $f(i,j)$ 来表示老张从 $i$ 走到 $j$ 时灯的总能耗。接下来考虑状态转移，即关灯的选择。

       因为老李的位置未知，初步判断 $f(i,j)$ 可以分别由 $f(i+1,j)$ 和 $f(i,j+1)$ ，代表着老李两个不同的行进方向。但是问题又来了，转移的时候，并不知道老李的位置，可是老李的位置又和灯的耗能息息相关，因此我们必须要表示出老李的位置。于是定义状态 $f(i,j,0)$ 表示老李关掉了 $i$ 到 $j$ 的灯且最后站在 $i$ 点时灯的总能耗，$f(i,j,1)$ 表示老李关掉了 $i$ 到 $j$ 的灯且最后站在 $j$ 点时灯的总能耗。

        $f(i,j,0)$ 可以由 $f(i+1,j,0)$ 转移（向左走一步关掉 $i$ 处的灯），也可以由 $f(i+1,j,1)$ 转移（掉头关掉 $i$ 处的灯），而$f(i,j,1)$ 同理，；转移时根据老李的行走时间计算灯的耗能。

代码

#include<iostream>
#include<cstring>
#define maxn 60
using namespace std;
int n, c, a[maxn], sum[maxn], f[maxn][maxn][2];
int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> n >> c;
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i] >> sum[i];
		sum[i] += sum[i - 1];
	}
	memset(f, 5, sizeof(f));
	f[c][c][0] = f[c][c][1] = 0;
	for(int L=2;L<=n;L++)
		for (int i = 1, j = i + L - 1; j <= n; i++, j++)
		{
			f[i][j][0] = min(f[i + 1][j][0] + (a[i + 1] - a[i]) * (sum[n] - sum[j] + sum[i]),
				f[i + 1][j][1] + (a[j] - a[i]) * (sum[n] - sum[j] + sum[i]));
			f[i][j][1] = min(f[i][j - 1][0] + (a[j] - a[i]) * (sum[n] - sum[j - 1] + sum[i - 1]),
				f[i][j - 1][1] + (a[j] - a[j - 1]) * (sum[n] - sum[j - 1] + sum[i - 1]));
		}
	cout << min(f[1][n][1], f[1][n][0]);
	return 0;
}

这篇关于P1220 关路灯的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！