好的网站制作平台,品牌型网站设计,网站上传后后台进不去,义乌电子商务有限公司正题
评测记录:https://www.luogu.org/recordnew/lists?uid52918pidP1220 题目大意
有n盏灯#xff0c;每个灯的所在位置和1s消耗的能量不同#xff0c;现在一个人在c号灯下#xff0c;他行走速度1m/s#xff0c;他走到的地方灯会熄灭#xff0c;求最少消耗能量。…正题
评测记录:https://www.luogu.org/recordnew/lists?uid52918pidP1220 题目大意
有n盏灯每个灯的所在位置和1s消耗的能量不同现在一个人在c号灯下他行走速度1m/s他走到的地方灯会熄灭求最少消耗能量。 解题思路
用fi,j,0/1f_{i,j,0/1}fi,j,0/1表示已经熄灭i∼ji\sim ji∼j这个范围的灯人在i处或j处。 然后我们考虑如果人在i处那么可以从i1处过来 fi1,j,0(li1−li)∗(sn−sjsi)f_{i1,j,0}(l_{i1}-l_i)*(s_n-s_js_i)fi1,j,0(li1−li)∗(sn−sjsi) 或者从j折返 fi1,j,1(lj−li)∗(sn−sjsi)f_{i1,j,1}(l_j-l_i)*(s_n-s_js_i)fi1,j,1(lj−li)∗(sn−sjsi) 右边的话以此类推
动态转移 f[i][j][0]min(f[i1][j][0](l[i1]-l[i])*(s[n]-s[j]s[i]),f[i][j][0]);f[i][j][0]min(f[i1][j][1](l[j]-l[i])*(s[n]-s[j]s[i]),f[i][j][0]);f[i][j][1]min(f[i][j-1][1](l[j]-l[j-1])*(s[n]-s[j-1]s[i-1]),f[i][j][1]);f[i][j][1]min(f[i][j-1][0](l[j]-l[i])*(s[n]-s[j-1]s[i-1]),f[i][j][1]);code
#includecstdio
#includealgorithm
#includecstring
#define N 60
using namespace std;
int n,c,l[N],f[N][N][2],J,s[N];
int main()
{memset(f,127,sizeof(f));//初始化scanf(%d%d,n,c);for(int i1;in;i)scanf(%d%d,l[i],J),s[i]s[i-1]J;//前缀和f[c][c][0]f[c][c][1]0;for(int len2;lenn;len)//枚举区间长度for(int i1;ilen-1n;i)//枚举左端点{int jilen-1;//计算又端点f[i][j][0]min(f[i1][j][0](l[i1]-l[i])*(s[n]-s[j]s[i]),f[i][j][0]);f[i][j][0]min(f[i1][j][1](l[j]-l[i])*(s[n]-s[j]s[i]),f[i][j][0]);f[i][j][1]min(f[i][j-1][1](l[j]-l[j-1])*(s[n]-s[j-1]s[i-1]),f[i][j][1]);f[i][j][1]min(f[i][j-1][0](l[j]-l[i])*(s[n]-s[j-1]s[i-1]),f[i][j][1]);//动态转移}printf(%d,min(f[1][n][0],f[1][n][1]));
}
