先附上我最开始的想法 记忆化搜索
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> using namespace std; int n,m,i,ans; int sum1[55],sum2[55],s[55],p[55]; int jiyi[55][55][2]; int dp(int a,int b,int z){ int fanhui=jiyi[a][b][z]; if(fanhui!=0){ return fanhui; }else{ if(a==1&&b==n){ fanhui=0; } else{ if(a==1){ if(z==0){ fanhui=dp(a,b+1,1)+sum2[b+1]*(s[b+1]-s[a]); } else{ fanhui=dp(a,b+1,1)+sum2[b+1]*(s[b+1]-s[b]); } } else{ if(b==n){ if(z==0){ fanhui=dp(a-1,b,0)+sum1[a-1]*(s[a]-s[a-1]); }else{ fanhui=dp(a-1,b,0)+sum1[a-1]*(s[b]-s[a-1]); } } else{ if(z==0){ fanhui=dp(a-1,b,0)+(sum1[a-1]+sum2[b+1])*(s[a]-s[a-1]); fanhui=min(fanhui,dp(a,b+1,1)+(sum1[a-1]+sum2[b+1])*(s[b+1]-s[a])); } else{ fanhui=dp(a-1,b,0)+(sum1[a-1]+sum2[b+1])*(s[b]-s[a-1]); fanhui=min(fanhui,dp(a,b+1,1)+(sum1[a-1]+sum2[b+1])*(s[b+1]-s[b])); } } } } } return fanhui; } int main(){ cin>>n>>m; for(i=1;i<=n;i++){ cin>>s[i]; cin>>p[i]; } sum1[0]=0; sum1[n+1]=0; for(i=1;i<=n;i++){ sum1[i]=sum1[i-1]+p[i]; } for(i=n;i>=1;i--){ sum2[i]=sum2[i+1]+p[i]; } ans=dp(m,m,0); cout<<ans; return 0; }
这个程序本身是可以运行的 但是时间复杂度不允许，在洛谷数据中TLE了5个点
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> using namespace std; int n,m,v[55],ans=0x7fffffff; struct sty{ int x,w; }a[55]; //当前位置，已经关了的点，当前时间，当前总耗电，当前没关的灯的总功率。 int min(int a,int b){ if(a>b) return b; return a; } void dfs(int now,int num,int t,int sum,int su) { if(sum+su*t>=ans) return; if(num==n-1) { ans=min(ans,sum); return; } for(int i=1;i<=n;++i){ if(now+i<=n&&!v[now+i]){ int t1=fabs(a[now].x-a[now+i].x); v[now+i]=1; dfs(now+i,num+1,t+t1,sum+a[now+i].w*(t+t1),su-a[now+i].w); v[now+i]=0; break; } } for(int i=-1;i>=-n;--i) if(now+i>=1&&!v[now+i]){ int t2=fabs(a[now].x-a[now+i].x); v[now+i]=1; dfs(now+i,num+1,t+t2,sum+a[now+i].w*(t+t2),su-a[now+i].w); v[now+i]=0; break; } } int main() { int su=0; cin>>n>>m; for(int i=1;i<=n;++i){ scanf("%d%d",&a[i].x,&a[i].w); if(i!=m) su+=a[i].w;///统计除了出生点以外的所有点的总功率 } v[m]=1; dfs(m,0,0,0,su); cout<<ans<<endl; return 0; }
这一套是经过剪枝后的记忆化搜索，
第一次加的判定是if(sum>ans)return ;这个很好理解，就是当前耗电大于答案，剪掉。
第二次是if(sum+（当前已用的时间）*(当前没关的灯的总功率)>ans)return ;
但仍然考试中TLE五个点= =
然而这题的正统方法是区间DP
先附上AC代码：
#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 {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; }
其中f【i】【j】【0/1】是指当前关闭i-j的灯并且站在了i（三维数是0）或j（三维数是1）
因为数据范围很和谐，所以三维轻松AC
自定义min max是因为害怕会因为这一点点的时间而TLE