题意
给你每盏路灯的位置与单位时间内的耗电量，以及你的出发位置以及单位时间内移动的距离，求在你关闭所有的路灯之前，最小的耗电总量。（一个路灯被关闭后就不再耗电）
解法
这道题与lrj的算法入门经典P293的那一道题差不多，通过分析我们知道，在任意时刻，已经关掉的灯构成一个区间，并且人一定在这个区间的左端点或者右端点（因为如果你为了关掉一个灯而路过了另一个灯，那么你一定会将路过的灯都关掉）。于是我们设 \(dp[i][j][0]\) 表示现在已经关掉灯的区间为 \([i,j]\) 且人在左端点， \(dp[i][j][1]\) 表示现在已经关掉灯的区间为 \([i,j]\) 且人在右端点。于是有转移方程：
$ dp[i][j][0] = min(dp[i+1][j][0] + cost(i,i+1) , dp[i+1][j][1] + cost(j,i)) $ $ dp[i][j][1] = min(dp[i][j-1][0] + cost(i,j) , dp[i][j-1][1] + cost(j,j-1)) $ 其中 $ cost(i,j) $ 为人从 i 走到 j 的时间中其它未关闭的灯的耗电量。代码
#include#include #include #include #include #include #include #define INF 2139062143#define MAX 0x7ffffffffffffff#define del(a,b) memset(a,b,sizeof(a))using namespace std;typedef long long ll;template inline void read(T&x){ x=0;T k=1;char c=getchar(); while(!isdigit(c)){if(c=='-')k=-1;c=getchar();} while(isdigit(c)){x=x*10+c-'0';c=getchar();}x*=k;}const int maxn=50+5;int dp[maxn][maxn][2];int pos[maxn];int sum[maxn];int n,c;int main(){ read(n),read(c); for(int i=1,w;i<=n;i++) { read(pos[i]),read(w); sum[i]=sum[i-1]+w; } for(int i=1;i<=n;i++) dp[i][i][0]=dp[i][i][1]=sum[n]*abs(pos[i]-pos[c]);//因为只熄灭了一个灯，所以所有的灯都燃烧了那么久。 for(int len=2;len<=n;len++) for(int i=1;i+len-1<=n;i++){ int j=i+len-1; dp[i][j][0]=min( dp[i+1][j][0]+abs(pos[i+1]-pos[i])*(sum[i]+sum[n]-sum[j]), dp[i+1][j][1]+abs(pos[j]-pos[i])*(sum[i]+sum[n]-sum[j])); dp[i][j][1]=min( dp[i][j-1][1]+abs(pos[j-1]-pos[j])*(sum[i-1]+sum[n]-sum[j-1]), dp[i][j-1][0]+abs(pos[i]-pos[j])*(sum[i-1]+sum[n]-sum[j-1])); } printf("%d",min(dp[1][n][0],dp[1][n][1])); return 0;}