104 条题解
-
10
PowderHan LV 10 @ 2017-05-08 09:10:20
/* 经典好题~一个dp必学题叭~~ 首先我们要想怎么样才能完整表示一个状态~ 我们可以看到的 如果去关灯关掉了区间[l,r]的灯 那么最后关的一盏不是l就是r 所以我们可以想到用这样一个状态表示 f[l][r][k]表示关掉区间[l,r]的所有灯所需要的最小代价 其中k=0表示现在人在l即最后关的灯是l k=1表示现在人在r即最后关的是r这盏灯 这样就设计出了一个正确无误的状态 先考虑初值 f[i][i]就是从起始位置直接到i开i灯的代价 那么我们来考虑状态转移 我们知道f[l][r][0]表示的是最后关掉了l这盏灯使得[l,r]全部都关了 那么对应的上一个状态必然是已经关掉了[l+1,r]区间所有的灯 那么我们就要考虑到到底是f[l+1][r][0]转移过来更优还是f[l+1][r][1]更优 即考虑到了左右两种完全的情况 那么很容易有状态转移 f[i][j][0]=min(f[i+1][j][0]+(sump-(s[i+1][j]))*getd(i,i+1), f[i+1][j][1]+(sump-(s[i+1][j]))*getd(i,j)); 其中我们已经预处理出sump表示所有灯总功率 s[i]表示1...i的所有灯的功率然后用前缀和可以算出s[i+1][j] 这个转移仔细理解一下就好了 同理就可以得出f[i][j][1]的转移 递推的时候外层循环枚举长度内层循环枚举起点 最后取f[1][n][0]和f[1][n][1]的更优值就好了~ 时间复杂度O(n^2) 可以直接秒杀~ */ #include <iostream> #include <cstdio> #include <algorithm> #include <cstring> using namespace std; const int MAXN=52; int f[MAXN][MAXN][2]; int d[MAXN]; int s[MAXN]; int sump; int n,poss; void init() { int p; scanf("%d%d",&n,&poss); for(int i=1;i<=n;i++) { scanf("%d%d",&d[i],&p); s[i]=s[i-1]+p; sump+=p; } } inline int getd(int x,int y) { return abs(d[x]-d[y]); } void DP() { memset(f,0x37,sizeof(f)); for(int i=1;i<=n;i++) f[i][i][0]=f[i][i][1]=abs(d[i]-d[poss])*sump; for(int l=2;l<=n;l++) for(int i=1;i<=n&&i<=n-l+1;i++) { int j=i+l-1; f[i][j][0]=min(f[i+1][j][0]+(sump-(s[j]-s[i]))*getd(i,i+1), f[i+1][j][1]+(sump-(s[j]-s[i]))*getd(i,j)); f[i][j][1]=min(f[i][j-1][0]+(sump-(s[j-1]-s[i-1]))*getd(i,j), f[i][j-1][1]+(sump-(s[j-1]-s[i-1]))*getd(j-1,j)); } cout<<min(f[1][n][0],f[1][n][1])<<endl; } int main() { init(); DP(); } -
1
#include <cstdio>
#include <cstring>
using namespace std;
const int MAXM=60;
int a[MAXM],b[MAXM],sum[MAXM],n,m,c;
int f[MAXM][MAXM][2];
int min(int a,int b)//这一点希望大家注意：最好max和min函数自己写，会有效的加快程序速度
{return a<b?a:b;}
int max(int a,int b)
{return a>b?a:b;}
int main()
{
scanf("%d%d",&n,&c);
memset(f,127,sizeof(f));//赋成极大值防止后面的min出问题
for(int i=1;i<=n;i++)
scanf("%d%d",&a[i],&b[i]),sum[i]=sum[i-1]+b[i];
f[c][c][0]=f[c][c][1]=0;//瞬间被关（初始化）
for(int l=2;l<=n;l++)
for(int i=1;i+l-1<=n;i++)
{
int j=i+l-1;
f[i][j][0]=min(f[i+1][j][0]+(a[i+1]-a[i])*(sum[i]+sum[n]-sum[j]),//继续走下去会更快吗？
f[i+1][j][1]+(a[j]-a[i])*(sum[i]+sum[n]-sum[j]));//还是从j点折返回来会更快？（此时假设[i+1][j]被关，i亮，从j端点往回赶去关i）
//要注意的一点是sum[n]-(sum[j]-sum[i])是包括了i这一点的电能的，因为走过来的过程中灯i也会耗电
f[i][j][1]=min(f[i][j-1][0]+(a[j]-a[i])*(sum[i-1]+sum[n]-sum[j-1]),//同上
f[i][j-1][1]+(a[j]-a[j-1])*(sum[i-1]+sum[n]-sum[j-1]));
}
int ans=min(f[1][n][0],f[1][n][1]);
printf("%d",ans);
return 0;
} -
1
-
1
-
1
#include <cstdio> #include <cstring> #include <algorithm> #include <iostream> typedef long long lg; #define MAXX 200 #define min(a,b) (a<b?a:b) //#define OPENFILE struct Data { int x,v; }a[MAXX]; lg sum[MAXX],f[MAXX][MAXX][2]; int n,c; bool comp(const Data a,const Data b) { if(a.x==b.x) return a.v<b.v; return a.x<b.x; } int main(int argc, char** argv) { # ifdef OPENFILE freopen("data.in","r",stdin); # endif scanf("%d%d",&n,&c); for(int i=1;i<=n;i++) scanf("%d%d",&a[i].x,&a[i].v); std::sort(a+1,a+n+1,comp); for(int i=1;i<=n;i++) sum[i]=sum[i-1]+a[i].v; for(int i=1;i<=n;i++) f[i][i][0]=f[i][i][1]=abs(a[i].x-a[c].x)*sum[n]; //std::cout<<sum[1]<<"\n"; for(int j=2;j<=n;j++) for(int i=1;i+j-1<=n;i++) { int k=i+j-1; lg summ=sum[n]-sum[k]+sum[i]; f[i][k][0]=min(f[i+1][k][0]+abs(a[i].x-a[i+1].x)*summ,f[i+1][k][1]+abs(a[k].x-a[i].x)*summ); summ=sum[n]-sum[k-1]+sum[i-1]; f[i][k][1]=min(f[i][k-1][1]+abs(a[k-1].x-a[k].x)*summ,f[i][k-1][0]+abs(a[i].x-a[k].x)*summ); } printf("%ld",(min(f[1][n][0],f[1][n][1]))); return 0; } -
1
wang_yanheng LV 10 @ 2016-04-06 17:56:34
感谢S.Y.F大牛的题解。说明2点：
1. 所有数据中距离都是排好序的，不必特殊处理。
2. 有人说第一个点有50个空行，需要特判，其实不必。f[l,r,k] 表示已经关掉[l,r]区间时最小总消耗。k=0表示人在 l 处；k=1表示人在 r 处
\(
f[l,r,0] = min \{ f[l+1,r,0] + (P-sum[l+1,r])*dist[l,l+1], f[l+1,r,1] + (P-sum[l+1,r])*dist[l,r] \} \\
f[l,r,1] = min \{ f[l,r-1,1] + (P-sum[l,r-1])*dist[r-1,r], f[l,r-1,0] + (P-sum[l,r-1])*dist[l,r] \}
\)其中 P 是所有灯的功率之和，sum[l,r]=区间[l,r]内灯的功率之和，dist[l,r]=l到r的距离。
sum和dist都预处理出来即可。
放一段核心代码（pos 是人的初始位置）for(l=pos; l>=1; l--){
for(r=pos; r<=num; r++){
if(l < pos)
f[l][r][0] = Min(f[l+1][r][0] + (P-sum[l+1][r])*dist[l][l+1], f[l+1][r][1] + (P-sum[l+1][r])*dist[l][r]);
if(r > pos)
f[l][r][1] = Min(f[l][r-1][1] + (P-sum[l][r-1])*dist[r-1][r], f[l][r-1][0] + (P-sum[l][r-1])*dist[l][r]);
}
} -
1
#include<iostream>
using namespace std;
int f[57][57][2] = {0}, w[57][57] = {0}, l[57][57] = {0};
int n, m, wh[57], p[57];
int sum;
void pre(int a, int b)
{
for(int i = a; i <= b; i++)
{
w[a][b] += p[i];
}
l[a][b] = wh[b] - wh[a];
}int main()
{
cin >> n >> m;
for(int i = 1; i <= n; i++)
cin >> wh[i] >> p[i];
for(int i = 1; i <= n; i++)
for(int j = i; j <= n; j++)
pre(i, j);
sum = w[1][n];
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
for(int k = 0; k <= 1; k++)
f[i][j][k] = 10000000;
f[m][m][1] = 0; f[m][m][0] = 0;
for(int k = 1; k <= n; k++)
{
for(int i = 1; i <= n - k; i++)
{
int j = i + k;
f[i][j][0] = min(f[i + 1][j][0] + (sum - w[i + 1][j]) * l[i][i + 1], f[i + 1][j][1] + (sum - w[i + 1][j]) * l[i][j]);
f[i][j][1] = min(f[i][j - 1][1] + (sum - w[i][j - 1]) * l[j - 1][j], f[i][j - 1][0] + (sum - w[i][j - 1]) * l[i][j]);
// cout << f[i][j][0] << " " << f[i][j][1] << endl;
}
}
cout << min(f[1][n][0], f[1][n][1]);
return 0;
}
参考楼上大神（们）的想法。。。因为没有c++的，冒昧发一篇，希望有用 -
0
HLBhahaqiu LV 8 @ 2020-12-11 21:27:25
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;const int MAXN=52;
int f[MAXN][MAXN][2];
int d[MAXN];
int s[MAXN];
int sump;
int n,poss;void init()
{
int p;
scanf("%d%d",&n,&poss);
for(int i=1;i<=n;i++)
{
scanf("%d%d",&d[i],&p);
s[i]=s[i-1]+p; sump+=p;
}
}inline int getd(int x,int y)
{
return abs(d[x]-d[y]);
}void DP()
{
memset(f,0x37,sizeof(f));
for(int i=1;i<=n;i++)
f[i][i][0]=f[i][i][1]=abs(d[i]-d[poss])*sump;
for(int l=2;l<=n;l++)
for(int i=1;i<=n&&i<=n-l+1;i++)
{
int j=i+l-1;
f[i][j][0]=min(f[i+1][j][0]+(sump-(s[j]-s[i]))*getd(i,i+1),
f[i+1][j][1]+(sump-(s[j]-s[i]))*getd(i,j));
f[i][j][1]=min(f[i][j-1][0]+(sump-(s[j-1]-s[i-1]))*getd(i,j),
f[i][j-1][1]+(sump-(s[j-1]-s[i-1]))*getd(j-1,j));
}
cout<<min(f[1][n][0],f[1][n][1])<<endl;
}int main()
{
init();
DP();
} -
0
#include <iostream>
#include <cstring>
using namespace std;
long long n,s,a[1001],w[1001];
long long t[1001][1001],f[1001][1001][2];
int main()
{
int i,j,l;
cin>>n>>s;
for(i=1;i<=n;i++)
cin>>a[i]>>w[i];
for(i=1;i<=n;i++)
for(j=i;j<=n;j++)
t[i][j]=t[i][j-1]+w[j];
int sum=t[1][n];
for(i=1;i<=n;i++)
for(j=i;j<=n;j++)
t[i][j]=sum-t[i][j];
memset(f,1,sizeof f);
f[s][s][0]=f[s][s][1]=0;
for(l=2;l<=n;l++)
for(i=1;i<=n-l+1;i++)
{
int j=i+l-1;
f[i][j][0]=min(f[i+1][j][0]+t[i+1][j]*(a[i+1]-a[i]),f[i+1][j][1]+t[i+1][j]*(a[j]-a[i]));
f[i][j][1]=min(f[i][j-1][1]+t[i][j-1]*(a[j]-a[j-1]),f[i][j-1][0]+t[i][j-1]*(a[j]-a[i]));
}
cout<<min(f[1][n][0],f[1][n][1]);
return 0;
} -
0
/*其实这道区间DP还是值得一做，经典题思考起来总是那么吃力却非常满足~~
思路如下：
对于左右区间DP，状态有俩种：
A.向左 B.向右
经过~~借鉴大佬后~~我~~们~~不妨用一个多维dp来储存状态：dp[i][j]k；
其中1为右位，0为左位
对于dp[i][j]1可从dp[i+1][j]0
和dp[i+1][j]1 ，最后注意的一点是i，j的顺序问题（这里就不再赘述）*/
cpp
#include<iostream>
#include<cstring>
#define M 60//大点
using namespace std;
int dp[M][M][2],e[M],d[M];
int eng[M];
int minx(int x,int y)
{
return x<y?x:y;
}
int main()
{
int n,c;
ios::sync_with_stdio(false);//取消联系，飞的更快
cin>>n>>c;
memset(eng,0,sizeof(eng));
memset(dp,127,sizeof(dp));//初始化
dp[c][c][0]=dp[c][c][1]=0;
for (register int i=1;i<=n;i++) {
cin>>d[i]>>e[i];//e为消耗量，d为距离
eng[i]=eng[i-1]+e[i];//用一个前缀和储存损失的能量
}
for (register int j=c;j<=n;j++)
for (register int i=j-1;i>=1;i--)
{
int e1_go=(d[i+1]-d[i])*(eng[n]+eng[i]-eng[j]);//去的损失能量
int e1_bk=(d[j]-d[i])*(eng[n]+eng[i]-eng[j]);//回的损失能量，下同
int e2_go=(d[j]-d[j-1])*(eng[n]+eng[i-1]-eng[j-1]);
int e2_bk=(d[j]-d[i])*(eng[n]+eng[i-1]-eng[j-1]);
dp[i][j][0]=minx(dp[i+1][j][0]+e1_go,dp[i+1][j][1]+e1_bk);
dp[i][j][1]=minx(dp[i][j-1][1]+e2_go,dp[i][j-1][0]+e2_bk);
}
int ans=minx(dp[1][n][0],dp[1][n][1]);//最后比较是在左端还是在右端更小
cout<<ans;
return 0;
}
蒟蒻程序，大佬指教
~~~· -
0
/*借鉴大佬的*/
#include<bits/stdc++.h>
using namespace std;
int f[2017][2017],dp[2000][2000][3];
int a[2017],b[2017],n,m,v=0,x,y,c;
int main()
{
scanf("%d%d",&n,&c);
for(int i=1;i<=n;i++)
scanf("%d%d",&a[i],&b[i]),b[i]+=b[i-1];
memset(dp,127,sizeof(dp));
dp[c][c][0]=dp[c][c][1]=0;
for(int i=c;i>=1;i--)
for(int j=i+1;j<=n;j++)
{
dp[i][j][0]=min(dp[i][j][0],dp[i+1][j][0]+(a[i+1]-a[i])*(b[n]-(b[j]-b[i])));
dp[i][j][0]=min(dp[i][j][0],dp[i+1][j][1]+(a[j]-a[i])*(b[n]-(b[j]-b[i])));
dp[i][j][1]=min(dp[i][j][1],dp[i][j-1][1]+(a[j]-a[j-1])*(b[n]-(b[j-1]-b[i-1])));
dp[i][j][1]=min(dp[i][j][1],dp[i][j-1][0]+(a[j]-a[i])*(b[n]-(b[j-1]-b[i-1])));
}
printf("%d\n",min(dp[1][n][0],dp[1][n][1]));
return 0;
} -
0
-
0
Sky1231 (sky1231) LV 10 @ 2017-07-30 17:43:33
#include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <iomanip> #include <iostream> #include <algorithm> #include <vector> #include <deque> #include <limits> #include <string> #include <sstream> using namespace std; const int oo_min=0xcfcfcfcf,oo_max=0x3f3f3f3f; struct segment_tree_1 { int l,r,mid,x; }st[2*64+2]; int n,m; int a[51+1]; int p[51+1]; int f[51+1][51+1][1+1]; void build_segment_tree_1(int now,int l,int r) { st[now].l=l,st[now].r=r,st[now].mid=(l+r)/2; if (l<r) { if (l<=st[now].mid) build_segment_tree_1(now*2,l,st[now].mid); if (st[now].mid+1<=r) build_segment_tree_1(now*2+1,st[now].mid+1,r); } if (l==r) st[now].x=p[l]; else st[now].x=st[now*2].x+st[now*2+1].x; } int sum_1(int now,int l,int r) { if (l>r) return 0; else if (st[now].l==l&&r==st[now].r) return st[now].x; else if (r<=st[now].mid) return sum_1(now*2,l,r); else if (st[now].mid+1<=l) return sum_1(now*2+1,l,r); else return sum_1(now*2,l,st[now].mid)+sum_1(now*2+1,st[now].mid+1,r); } int main() { scanf("%d%d",&n,&m); for (int i=1;i<=n;i++) scanf("%d%d",&a[i],&p[i]); build_segment_tree_1(1,1,n); memset(f,oo_max,sizeof(f)); f[m][m][0]=f[m][m][1]=0; for (int l=1;l<=n;l++) for (int i=1;i<=n-l+1;i++) { int j=i+l-1; f[i][j][0]=min(f[i][j][0],f[i+1][j][0]+(sum_1(1,1,n)-sum_1(1,i+1,j))*(a[i+1]-a[i])); f[i][j][0]=min(f[i][j][0],f[i+1][j][1]+(sum_1(1,1,n)-sum_1(1,i+1,j))*(a[j]-a[i])); f[i][j][1]=min(f[i][j][1],f[i][j-1][0]+(sum_1(1,1,n)-sum_1(1,i,j-1))*(a[j]-a[i])); f[i][j][1]=min(f[i][j][1],f[i][j-1][1]+(sum_1(1,1,n)-sum_1(1,i,j-1))*(a[j]-a[j-1])); } printf("%d\n",min(f[1][n][0],f[1][n][1])); } -
0
cdqzgxxqdql LV 10 @ 2016-10-20 16:50:59
#include<cstdio> #include<iostream> #include<cstring> using namespace std; int pos[51],w[51],sum[51][51]; int f[51][51][2],tot; int main() { int n,c; cin>>n>>c; for(int i=1;i<=n;i++) { cin>>pos[i]>>w[i]; tot+=w[i]; } sum[1][1]=w[1]; for(int i=2;i<=n;i++) { sum[1][i]=sum[1][i-1]+w[i]; sum[i][i]=w[i]; } for(int i=2;i<=n;i++) for(int j=i+1;j<=n;j++) sum[i][j]=sum[i][j-1]+w[j]; memset(f,127/3,sizeof f); f[c][c][0]=f[c][c][1]=0; int l,r; for(int i=c;i>=1;i--) for(int j=c;j<=n;j++) { if(i<c) f[i][j][0]=min(f[i+1][j][0]+(pos[i+1]-pos[i])*(tot-sum[i+1][j]),f[i+1][j][1]+(pos[j]-pos[i])*(tot-sum[i+1][j])); if(c<j) f[i][j][1]=min(f[i][j-1][1]+(pos[j]-pos[j-1])*(tot-sum[i][j-1]),f[i][j-1][0]+(pos[j]-pos[i])*(tot-sum[i][j-1])); l=f[i][j][0],r=f[i][j][1]; } printf("%d",min(f[1][n][0],f[1][n][1])); }``` 感谢楼下大神题解 -
0
记录信息
评测状态 Accepted
题目 P1150 关路灯
递交时间 2016-06-15 11:41:49
代码语言 C++
评测机 ShadowShore
消耗时间 0 ms
消耗内存 580 KiB
评测时间 2016-06-15 11:41:50
评测结果
编译成功测试数据 #0: Accepted, time = 0 ms, mem = 572 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 576 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 576 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 576 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 576 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 572 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 576 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 572 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 576 KiB, score = 10
测试数据 #9: Accepted, time = 0 ms, mem = 580 KiB, score = 10
Accepted, time = 0 ms, mem = 580 KiB, score = 100
代码
#include<algorithm>
#include<cctype>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<ctime>
#include<iostream>
#include<string>
int f0[51][51],f1[51][51],s[51],p[51],n,m,temp;
inline int min(int x,int y)
{
x-=y;return y+(x&(x>>31));
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)
{
scanf("%d%d",&p[i],&temp);
s[i]=s[i-1]+temp;
f0[1][i]=f1[1][i]=f0[i][0]=f1[i][0]=f0[i][n+1]=f1[i][n+1]=1000000000;
}
f0[1][m]=0;f1[1][m]=0;
for(int i=2;i<=n;++i)
for(int j=1;j<=n;++j)
{
int &ff0=f0[i][j],&ff1=f1[i][j];
if(j+1<=n)
ff0=f0[i-1][j+1]+(s[j]+s[n]-s[j+i-1])*(p[j+1]-p[j]);
if(j+i-1<=n)
ff0=min(ff0,f1[i-1][j+i-1]+(s[j]+s[n]-s[j+i-1])*(p[j+i-1]-p[j]));
if(j>=2)
ff1=f1[i-1][j-1]+(s[j-i]+s[n]-s[j-1])*(p[j]-p[j-1]);
if(j-i>=0)
ff1=min(ff1,f0[i-1][j-i+1]+(s[j-i]+s[n]-s[j-1])*(p[j]-p[j-i+1]));
}
printf("%d",min(f0[n][1],f1[n][n]));
return 0;
} -
0
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long LL;
const int N = 200 + 24;
int n,m,sum[N];
struct node
{
int a,b;
}s[N];
LL dp[N][N][2];
LL dfs(int l, int r, int k)
{
if(dp[l][r][k] != -1)
return dp[l][r][k];
dp[l][r][k] = 1e16;
if(l == r)
return dp[l][r][k];
dp[l][r][0] = min(dp[l][r][0],dfs(l+1,r,0) + (sum[l]-sum[0] + sum[n] - sum[r])*abs(s[l + 1].a - s[l].a) );
dp[l][r][0] = min(dp[l][r][0],dfs(l+1,r,1) + (sum[l]-sum[0] + sum[n] - sum[r])*abs(s[r].a - s[l].a) );
dp[l][r][1] = min(dp[l][r][1],dfs(l,r - 1,0) + (sum[l-1]-sum[0] + sum[n] - sum[r - 1])*abs(s[r].a - s[l].a) );
dp[l][r][1] = min(dp[l][r][1],dfs(l,r - 1,1) + (sum[l-1]-sum[0] + sum[n] - sum[r - 1])*abs(s[r].a - s[r-1].a) );
return dp[l][r][k];
}
int main()
{
#ifdef CDZSC_OFFLINE
freopen("in.txt","r",stdin);
#endif //CDZSC_OFFLINE
while(~scanf("%d%d",&n,&m))
{
sum[0] = 0;
memset(dp,-1,sizeof(dp));
dp[m][m][0] = dp[m][m][1] = 0;
for(int i = 1; i <= (n == 50 ? 100 : n); i++)//超有病的第一个数据，n == 50 时有100个输入。坑人！
{
scanf("%d%d",&s[i].a,&s[i].b);
sum[i] = sum[i - 1] + s[i].b;
}
printf("%lld\n",min(dfs(1,n,0),dfs(1,n,1)));
}
} -
0
-
0
wangqihang LV 8 @ 2015-08-04 16:50:40
var n,c,i,j,sum:longint;
m,w:array[0..1100] of longint;
a,l,r:array[0..1005,0..1005] of longint;//a[i,j]表示除过从i到j之间的灯的功率，
//l,r表示关完灯停留下哪个方向
function min(a,b:longint):longint;
begin
if a<b then exit(a) else exit(b);
end;
begin
readln(n,c);
sum:=0;
for i:=1 to n do begin
readln(m[i],w[i]);
inc(sum,w[i]);
end;
for i:=1 to n do begin
a[i,i]:=sum-w[i];
for j:=i+1 to n do a[i,j]:=a[i,j-1]-w[j];
end;
for i:=c+1 to n do begin
r[c,i]:=r[c,i-1]+(m[i]-m[i-1])*a[c,i-1];//从原点向右关灯后停在i位置
l[c,i]:=r[c,i]+(m[i]-m[c])*a[c,i];//从原点向右关灯后返回到出发点c
end;
for i:=c-1 downto 1 do begin
l[i,c]:=l[i+1,c]+(m[i+1]-m[i])*a[i+1,c];//从原点向左关灯后停在i位置
r[i,c]:=l[i,c]+(m[c]-m[i])*a[i,c];//向左关灯后返回到出发点s
end;
for i:=c-1 downto 1 do
for j:=c+1 to n do begin
r[i,j]:=min(r[i,j-1]+(m[j]-m[j-1])*a[i,j-1],l[i,j-1]+(m[j]-m[i])*a[i,j-1]);
l[i,j]:=min(l[i+1,j]+(m[i+1]-m[i])*a[i+1,j],r[i+1,j]+(m[j]-m[i])*a[i+1,j]);
end;
writeln(min(l[1,n],r[1,n]));
end. -
0
这是我vj第一道交了三次才过的题目。一般都是一次AC的，而且这道题目改了我大半天。
有以下几个原因：
这种DP很经典，以前也看到过类似的一题，但没这么复杂，原来那题没有功率，只要考虑距离就行。
虽然如此，但当时对于DP方程的含义理解还是出了些问题；不过，查漏补缺本来就是好事，写个题解，就是为了加深影响，防止下次再出错误。首先，要明确，由于老头从中间开始，左右开始按灭灯，所以按灭的灯肯定是连续的。
即如果我当前在第5个位置，起始点在3，那第4盏灯肯定也是灭的。
这就启示我们，可以只枚举当前位置，和一共按灭的灯来初步确定方程f[i,j]:=f[i-1,j±i]+num(j,j±i);
为了方便起见，可以定义f[i,j,k]，表示已经按灭i栈灯，已按灭的连续的灯的起点j，显然这样就能确定f[j,j+i-1]这个区间了，再用k表示老头处于的位置，0表示在区间的左端，1表示在区间的右端。这样就省去了不少繁琐的递推过程，使问题简化。然后在考虑有fi,j可以推出那些状态。很显然，如果我要向左走，就能推出f[i+1,j-1]的区间；向右走，就能推出f[i+1,j]（仔细推敲区间的表示方式，可以画图帮助理解）.即3-4推出2-4或3-5；
再把k加进去。如果k=0，那些向左走，距离就是a[j]-a[j-1];如果k=1，那么向左走，就是a[i+j-1]-a[j-1].向右走也是同理。就留给大家自行思考了。对于每次走的那段距离，即我上面讲的。都会消耗任何一盏没有被按没的灯的能量。而没有按灭的灯单位时间消耗能量的总和，就是全部的功率tot减去已经按灭的灯的功率。因为已经按灭的灯是一个连续的区间sum（j-j+i-1），可以先预处理好sum的值，然后直接计算。
这样看来，方程似乎已经显而易见了： f[i+1,j-1,0]:=min(f[i,j,0]+(a[j]-a[j-1])*(tot-b[j+I-1]+b[j-1]),
f[i,j,1]+(a[j+i-1]-a[j-1])*(tot-b[j+i-1]+b[j-1]));
我的sum用前缀和的方式代替了，效果一样。上面一给出了想走左的方程，向右自行思考。
最后的答案就在min（f[n,1,1],f[n,1,0]）;至于边界和初始化，就不在多讲。如果你按我这样写，你会发现，连样例都过不去//我刚开始就是这样。
经过F7的单步调试，发现：在计算f[i,m]时，状态的继承会有问题。显然除了起始点，f[i,m]的值肯定是maxlongint。
所以应该把m这个点中间点删掉。其余照旧即可。剩下就只有细节问题了。
DXE-SYF。 -
0
哈哈，一遍AC了。DP：f【i，j，1（0）】表示以老头为中心右边关了i个，左边关了j个，且人在右边（左边）时的代价。
可以证明，对于F[I,J]一定只有2种走法：一种是原本人在左边第j个灯跑到右边关第i个灯，一种是原本人在右边的第i-1个灯关掉
第i个灯。以下是核心代码：
if i-1>=0 then begin
f[i,j,1]:=min(f[i,j,1],f[i-1,j,0]+(sum-sm(c-j,c+i-1))*(l[c+i]-l[c-j]));
f[i,j,1]:=min(f[i,j,1],f[i-1,j,1]+
(sum-sm(c-j,c+i-1))*(l[c+i]-l[c+i-1]));
同理，当F[I,J,0]也可以这样。（sm是函数用来算左边第j个灯到右边第i个灯的消耗量，l是距离，代价就是两者相乘（不算被
关掉的那个灯，因为老头走到以后才关掉它，之前也消耗的））。
-L.G.S庆祝国庆节！-
liyinghaowei @ 2015-10-01 20:04:03
两年后今天膜拜
-
PowderHan
LV 10
@ 2017-05-08 09:10:20
