P1220 关路灯

由题意，这也是一道典型的区间dp

dp4步走

1：定义状态

dp[l][r][0/1]表示l~r的路灯全灭掉并且最后停在l/r的最小消耗

2：状态转移方程

dp[l][r][0]=min(dp[l+1][r][0]+(a[l+1]-a[l])(s[n]-s[r]+s[l]),dp[l+1][r][1]+(a[r]-a[l])(s[n]-s[r]+s[l]));//停在l

dp[l][r][1]=min(dp[l][r-1][0]+(a[r]-a[l])(s[n]-s[r-1]+s[l-1]),dp[l][r-1][1]+(a[r]-a[r-1])(s[n]-s[r-1]+s[l-1]));//停在r

停在l的状态转移方程可能由l+1或r转移而来停在r的状态转移方程可能由r-1或l转移而来而每次转移的消耗=上一次的位置到这一次的位置的绝对值（路程）*每一秒的消耗量

3：初始化

因为要求最小值（最小消耗量）所以要赋值最大值 memset(dp,0x3f,sizeof(dp));

而len==1的情况（l==r）时不合法

所以不用做任何操作

4：答案

最后关完所有路灯后可能停在1/n so: cout << min(dp[1][n][0],dp[1][n][1]);//最小值

5：注意

为了节约时间本体需要对消耗做一个前缀和

而初始位置 c 需要赋值为0 dp[c][c][0]=dp[c][c][1]=0;//不用消耗能量

附上代码：


#include<bits/stdc++.h>
const double PI=acos(-1.0);
using namespace std;
int read(){
	int sum=0,f=1;
	char ch=getchar();
	while (ch<'0' || ch>'9'){
		if (ch=='-'){
			f=-1;
		}
		ch=getchar();
	}
	while (ch>='0' && ch<='9'){
		sum=sum*10+ch-48;
		ch=getchar();
	}
	return sum*f;
}
void print(int x){
	if (x<0){
		putchar('-');
		x=-x;
	}
	if (x>9){
		print(x/10);
	}
	putchar(x%10+48);
	return;
}
long long dp[100][100][3];// dp[i][j][0/1]考虑i~j路灯全灭掉并且停在i/j的最小消耗 
long long a[100];
long long w[100];
long long s[100];
int main(){
	long long n,c;
	cin >> n >> c;
	for (int i=1;i<=n;i++){
		cin >> a[i] >> w[i];
	}
	for (int i=1;i<=n;i++){
		s[i]=s[i-1]+w[i];//前缀和 
	}
	memset(dp,0x3f,sizeof(dp));//求最小值赋值最大值 
	dp[c][c][0]=dp[c][c][1]=0;//初始位置 
	for (int len=1;len<=n;len++){//长度 
		for (int l=1;l+len-1<=n;l++){//起点 
			long long r=l+len-1;//终点 
			if (len==1){//不用赋值 
				//不合法 
			}
			else{
				dp[l][r][0]=min(dp[l+1][r][0]+(a[l+1]-a[l])*(s[n]-s[r]+s[l]),dp[l+1][r][1]+(a[r]-a[l])*(s[n]-s[r]+s[l]));//停在i 
				dp[l][r][1]=min(dp[l][r-1][0]+(a[r]-a[l])*(s[n]-s[r-1]+s[l-1]),dp[l][r-1][1]+(a[r]-a[r-1])*(s[n]-s[r-1]+s[l-1]));//停在j 
			}
		}
	}
	cout << min(dp[1][n][0],dp[1][n][1]);//停在1/n的最小功耗 
	return 0;
}

新手小白，请多多指教

文章操作

相关推荐

评论

P1220 关路灯