histcat

Problem#

In a certain village, $n$ street lights have been installed along a road, each with varying power (i.e., consuming different amounts of electricity over the same period). Old Zhang lives next to one of these street lights in the middle of the road, and his job is to turn off these street lights one by one every morning at dawn.

To save electricity costs for the village, Old Zhang has recorded the position and power of each street light. He always tries to turn off the lights as quickly as possible, but he does not know how to turn them off in a way that minimizes electricity consumption. Every morning, he first turns off the street light next to him at dawn, and then he can go either left or right to turn off the lights. Initially, he thought that he could calculate the total power of the lights on the left and then the total power of the lights on the right, and choose to turn off the side with the higher power first, then return to turn off the lights on the other side. However, this is not the case, as turning back appropriately during the process may save more electricity.

Now it is known that Old Zhang walks at a speed of $1m/s$, and the position of each street light (an integer, i.e., the distance from the starting point of the road, in meters) and its power (in watts) are given. The time it takes for Old Zhang to turn off a light is very short and can be ignored.

Please write a program for Old Zhang to arrange the order of turning off the lights so that the total electricity consumption is minimized from the moment he starts turning off the lights (once a light is turned off, it no longer consumes electricity).

$1\le n\le50$, $1\le c\le n$.

Solution#

This problem is not easy to think of in terms of dynamic programming.

Then, based on a greedy approach, when going from point i to turn off the light at point j, all the lights passed will be turned off (taking no time), so we can determine that if the lights at points i and j are already turned off, then all the lights in the interval i...j are turned off, and the optimal strategy must end at either point i or point j.

Words from yinyuqin

So we define f[i][j][0/1] to represent the state of having turned off the lights from interval i to j, ending at i/j.

Note that during the transition, the light at point i/j has not been turned off yet, so it will consume electricity.

Problem#

Initialization!!!

Code#

#include<bits/stdc++.h>

using namespace std;

const int N = 55;

int read()
{
	int f = 1, x = 0;
	char ch = getchar();
	while(ch < '0' || ch > '9')
	{
		if(ch == '-') f = -1;
		ch = getchar();
	}

	while(ch >= '0' && ch <= '9')
	{
		x = x * 10 + ch - '0';
		ch = getchar();
	}
	return f * x;
}

struct U
{
	int pos, P;
}u[N];

int n, c;
int sum[N];
int f[N][N][2];//represents the current state of having turned off lights from i to j, with the last light turned off being at i/j, with the property: minimum electricity consumption 

int main()
{
	memset(f, 0x3f, sizeof f);
	n = read(), c = read();
	for(int i = 1;i <= n;i++)
	{
		u[i].pos = read(), u[i].P = read();
		sum[i] = sum[i - 1] + u[i].P;
	}

	f[c][c][1] = f[c][c][0] = 0;

	for(int L = 2; L <= n;L++)
	{
		for(int i = 1;i + L - 1 <= n;i++)
		{
			int j = i + L - 1;
			f[i][j][0] = min(f[i + 1][j][0] + (u[i + 1].pos - u[i].pos) * (sum[i]+sum[n]-sum[j]), f[i + 1][j][1] + (u[j].pos - u[i].pos) * (sum[i]+sum[n]-sum[j]));
			f[i][j][1] = min(f[i][j - 1][0] + (u[j].pos - u[i].pos) * (sum[i-1]+sum[n]-sum[j-1]), f[i][j - 1][1] + (u[j].pos - u[j - 1].pos) * (sum[i-1]+sum[n]-sum[j-1])); 
		}
	}


	cout << min(f[1][n][0], f[1][n][1]);
	return 0;
}