题目描述
某一村庄在一条路线上安装了 n 盏路灯, 每盏灯的功率有大有小 (即同一段时间内消耗的电量有多有少) 老张就住在这条路中间某一路灯旁, 他有一项工作就是每天早上天亮时一盏一盏地关掉这些路灯
为了给村里节省电费, 老张记录下了每盏路灯的位置和功率, 他每次关灯时也都是尽快地去关, 但是老张不知道怎样去关灯才能够最节省电他每天都是在天亮时首先关掉自己所处位置的路灯, 然后可以向左也可以向右去关灯开始他以为先算一下左边路灯的总功率再算一下右边路灯的总功率, 然后选择先关掉功率大的一边, 再回过头来关掉另一边的路灯, 而事实并非如此, 因为在关的过程中适当地调头有可能会更省一些
现在已知老张走的速度为 1m/s, 每个路灯的位置 (是一个整数, 即距路线起点的距离, 单位: m) 功率(W), 老张关灯所用的时间很短而可以忽略不计
请你为老张编一程序来安排关灯的顺序, 使从老张开始关灯时刻算起所有灯消耗电最少(灯关掉后便不再消耗电了)
输入输出格式
输入格式:
文件第一行是两个数字 n(1<=n<=50, 表示路灯的总数)和 c(1<=c<=n 老张所处位置的路灯号);
接下来 n 行, 每行两个数据, 表示第 1 盏到第 n 盏路灯的位置和功率数据保证路灯位置单调递增
输出格式:
一个数据, 即最少的功耗(单位: J,1J=1W.s)
输入输出样例
输入样例 #1: 复制
- 5 3
- 2 10
- 3 20
- 5 20
- 6 30
- 8 10
输出样例 #1: 复制
270
说明
输出解释:
{此时关灯顺序为 3 4 2 1 5, 不必输出这个关灯顺序}
- #include <bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- #define inf 0x39393939
- #define maxn 10000
- // 思想: 区间 dp(单位转换), 左右都可以自由转动的话, 那么专门开一维存左右位置(位置状态比方向状态要好)
- // 考虑区间 (i,j) 与之相关可以用来将其更新的有 (i+1,j) (i,j-1)
- // 再加上一维(左 0, 右 1)
- //(i,j,0) -->(i+1,j,0),(i+1,j,1)
- //(i,j,1) -->(i,j-1,0),(i,j-1,1)
- // 状态转移:
- // 当前区间获得的最小总功率
- //dp[i][j][0]=min(dp[i+1][j][0]+sum(i+1,j)*(t[i+1]-t[i]),dp[i+1][j][1]+sum(i+1,j)*(t[j]-t[i]));
- //dp[i][j][1]=min(dp[i][j-1][0]+sum(i,j-1)*(t[j]-t[i]),dp[i][j-1][1]+sum(i,j-1)*(t[j]-t[j-1]));
- //sum(i,j)是 (i,j) 区间外的所有灯泡功率之和
- // 初始化:
- //dp[c][c][0]=0,dp[c][c][1]=0;
- int dp[55][55][2];
- int sum[55];
- int t[55];
- int n,c;
- int main()
- {
- cin>>n>>c;
- for(int i=1; i<=n; i++)
- {
- cin>>t[i]>>sum[i];
- sum[i]+=sum[i-1];
- }
- // memset(dp,127,sizeof(dp));// 不能填 128, 最多 127!!!
- fill(dp[0][0],dp[0][0]+6050,inf);
- dp[c][c][0]=dp[c][c][1]=0;
- for(int j=c; j<=n; j++)
- for(int i=j-1; i>=1; i--)
- {
- dp[i][j][0]=min(dp[i+1][j][0]+(sum[n]+sum[i]-sum[j])*(t[i+1]-t[i]),
- dp[i+1][j][1]+(sum[n]+sum[i]-sum[j])*(t[j]-t[i]));
- dp[i][j][1]=min(dp[i][j-1][0]+(sum[n]+sum[i-1]-sum[j-1])*(t[j]-t[i]),
- dp[i][j-1][1]+(sum[n]+sum[i-1]-sum[j-1])*(t[j]-t[j-1]));
- }
- cout<<min(dp[1][n][1],dp[1][n][0]);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2493686.html