题目描述
某一村庄在一条路线上安装了 n 盏路灯，每盏灯的功率有大有小（即同一段时间内消耗的电量有多有少）。老张就住在这条路中间某一路灯旁，他有一项工作就是每天早上天亮时一盏一盏地关掉这些路灯。
为了给村里节省电费，老张记录下了每盏路灯的位置和功率，他每次关灯时也都是尽快地去关，但是老张不知道怎样去关灯才能够最节省电。他每天都是在天亮时首先关掉自己所处位置的路灯，然后可以向左也可以向右去关灯。开始他以为先算一下左边路灯的总功率再算一下右边路灯的总功率，然后选择先关掉功率大的一边，再回过头来关掉另一边的路灯，而事实并非如此，因为在关的过程中适当地调头有可能会更省一些。
现在已知老张走的速度为 1m/s，每个路灯的位置（是一个整数，即距路线起点的距离，单位：m）、功率（W），老张关灯所用的时间很短而可以忽略不计。
请你为老张编一程序来安排关灯的顺序，使从老张开始关灯时刻算起所有灯消耗电最少（灯关掉后便不再消耗电了）。
输入格式
第一行是两个数字 n（表示路灯的总数）和 c（老张所处位置的路灯号）；
接下来 n 行，每行两个数据，表示第 1盏到第 n 盏路灯的位置和功率。数据保证路灯位置单调递增。
输出格式
一个数据，即最少的功耗
输入输出样例
输入
5 3
2 10
3 20
5 20
6 30
8 10
输出
270
样例解释
此时关灯顺序为 3 4 2 1 5。
数据范围
n、c<=50
1.dp
#include<bits/stdc++.h> using namespace std; const int N=55; int n,c; int dp[N][N][2];//dp[i][j][0]代表i-j灯灭后，最终位置在i时,其余灯的最小消耗 //dp[i][j][0]代表i-j灯灭后，最终位置在j时,其余灯的最小消耗 int a[N],b[N],sum[N]; int main(){ cin>>n>>c; for(int i=1;i<=n;i++){ cin>>a[i]>>b[i]; sum[i]=sum[i-1]+b[i]; } memset(dp,0x3f3f,sizeof(dp)); dp[c][c][0]=0;dp[c][c][1]=0;//所在位置灯即刻灭，其他灯并未产生消耗 for(int j=c;j<=n;j++){ for(int i=j-1;i>0;i--){ dp[i][j][0]=min(dp[i+1][j][0]+(a[i+1]-a[i])*(sum[n]-sum[j]+sum[i]), dp[i+1][j][1]+(a[j]-a[i])*(sum[n]-sum[j]+sum[i])); dp[i][j][1]=min(dp[i][j-1][0]+(a[j]-a[i])*(sum[n]-sum[j-1]+sum[i-1]), dp[i][j-1][1]+(a[j]-a[j-1])*(sum[n]-sum[j-1]+sum[i-1])); } } cout<<min(dp[1][n][0],dp[1][n][1])<<endl; return 0; }
2.dfs
#include<bits/stdc++.h> using namespace std; const int N=55; pair<int,int>p[N]; int n,c,res,ans=0x3f3f3f,all,vis[N]; void dfs(int now){ bool flag=false; if(res>ans)return ; int i=now; while(vis[i]&&i<n)i++; if(!vis[i]){ vis[i]=true; all-=p[now].second; res+=all*(p[i].first-p[now].first); dfs(i); vis[i]=false; res-=all*(p[i].first-p[now].first); all+=p[now].second; flag=true; i=now; } while(vis[i]&&i>1)i--; if(!vis[i]){ vis[i]=true; all-=p[now].second; res+=all*(p[now].first-p[i].first); dfs(i); vis[i]=false; res-=all*(p[now].first-p[i].first); all+=p[now].second; flag=true; } if(!flag&&ans>res)ans=res; } int main(){ cin>>n>>c; for(int i=1;i<=n;i++){ scanf("%d%d",&p[i].first,&p[i].second); if(i!=c){ vis[i]=false; } else vis[i]=true; all+=p[i].second; } dfs(c); cout<<ans<<endl; return 0; }