刷题记录:牛客NC15447wyh的问题

传送门:牛客

题目描述:

我国现在能源消耗非常严重，现在政府有这样一个工作，每天早上都需要把一些路灯关掉，但是他们想
让在关闭的过程中所消耗的能源是最少的，负责路灯关闭的工作人员以1m/s的速度进行行走，假设关闭
路灯的时候不需要花费任何的时间，请你编写一个程序，计算在给定路灯位置和每个路灯的消耗能源的
多少，求出当所有路灯关闭的时候所需要的最少能量
输入:
4
3
2 2
5 8
6 1
8 7
输出:
56

感觉这道题的解法也是挺妙的,反正我第一次是根本想不出来

主要思路:

1. 首先对于我们这种题目,前缀和是肯定需要想到的.并且按照一般的区间dp思维,我们有一种比较显然的想法就是使用一个$dp[i][j]$来记录区间[i,j]之间的路灯全部关闭之后需要的最少能量,但是显然的假设我们使用了这个想法,我们会发现我们很难进行转移,因为我们只是记录的区间,我们并不知道此时此刻最优的时候我们是在区间的左右哪个位置,就不知道对于我们的下一次转移需要花费多少的能量了.所以此时我们就会发现我们刚开始的$dp$的思想应该是错误的
2. 所以我们需要换一种想法,我们发现对于每一个区间我们最优的时候显然是在端点位置的,因为只有在端点的位置才是我们刚刚好走完这个区间的时候,并且假设我们不知道是在左右的那个端点我们就无法进行转移.所以我们需要记录我们的端点的位置.我们可以$使用dp[i][j]来记录i到j范围内在i位置的最小花费$$使用dp[j][i]来记录i到j范围内在j位置的最小花费$
3. 这样的话我们就开始考虑如何转移的问题了.我们会发现假设我们现在有一个区间$dp[i,j]$,那么显然的我们可以这个区间的左端点的右边一个位置进行转移,也就是$dp[i+1][j]$,并且我们也可以从这个区间的右端点移动到我们的左端点,也就是$dp[j][i+1]$,为什么可以从这两个点进行转移呢,因为我们可能在上一个区间时先去解决i+1再去解决j,也有可能先去j再去i+1,$dp[j][i]的转移和之类似$

下面是具体的代码部分:

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <string.h>
#include <stack>
#include <deque>
using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3f
#define root 1,n,1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {
	ll x=0,w=1;char ch=getchar();
	for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
	return x*w;
}
#define maxn 1000000
#define ll_maxn 0x3f3f3f3f3f3f3f3f
const double eps=1e-8;
int n,v;
struct Light{
	int d,w;
}light[maxn];
int dp[1010][1010];
int sum[maxn];
int main() {
	while(scanf("%d%d",&n,&v)!=EOF) {
		memset(dp,0x3f,sizeof(dp));
		memset(sum,0,sizeof(sum));
		memset(light,0,sizeof(light));
		for(int i=1;i<=n;i++) {
			light[i].d=read();light[i].w=read();
			sum[i]=sum[i-1]+light[i].w;
		}	
		dp[v][v]=0;
		for(int i=v;i>=1;i--) {
			for(int j=v;j<=n;j++) {
				int tot=sum[i]+sum[n]-sum[j];
				int tot2=sum[n]-sum[j-1]+sum[i-1];
				dp[i][j]=min(dp[i][j],dp[i+1][j]+tot*(light[i+1].d-light[i].d));
				//对于这部分的代码可能会有一点问题,因为假设你模拟之后就会发现刚开始往右走的时候
				//我们的dp[i][j]竟然一直都是inf!!是不是感到很奇怪
				//不要慌,因为假设我们的v就是左端点的话我们的dp[i][j]显然是没有什么用的,因为直接往左走即可,不需要回到左端点
				//并且当我们的i往左边走时,我们的dp[i][j]就不再是inf了
				dp[i][j]=min(dp[i][j],dp[j][i+1]+tot*(light[j].d-light[i].d));
				dp[j][i]=min(dp[j][i],dp[j-1][i]+tot2*(light[j].d-light[j-1].d));
				dp[j][i]=min(dp[j][i],dp[i][j-1]+tot2*(light[j].d-light[i].d));
			}
		}
		printf("%d\n",min(dp[1][n],dp[n][1]));
	}
	return 0;
}