最优解一定是将起点、终点以及所有必经点连接成一棵树,对于每条树边恰好走两次,而从起点到终点的一条路径只走一次。

考虑连通性DP,设$f[i][j][k][x]$表示考虑完前$i$个走道,第$i$个走道底部和上部是否存在于树中,底部和上部是否和起点连通,走一次的路径端点是底部还是上部时的最小代价。

时间复杂度$O(NA^2)$。

#include<cstdio>
const int N=360,inf=100000000;
int m,n,A,B,i,j,k,x,a,b,nj,nk,nx,w,v[N][30],f[N][4][4][2],ans;
inline void up(int&a,int b){a>b?(a=b):0;}
inline int sum(int x,int l,int r){
int t=v[x][r];
if(l)t-=v[x][l-1];
return t;
}
int main(){
scanf("%d%d%d%d",&m,&n,&A,&B);A++;
while(m--)scanf("%d%d",&i,&j),v[i][j]=1;
for(i=0;i<=n;i++)for(j=0;j<4;j++)for(k=0;k<4;k++)for(x=0;x<2;x++)f[i][j][k][x]=inf;
f[0][1][1][0]=-B;
for(i=1;i<=n;i++)for(j=1;j<=A;j++)v[i][j]+=v[i][j-1];
for(i=0;i<n;i++)for(j=0;j<4;j++)for(k=1;k<4;k++)for(x=0;x<2;x++)if(f[i][j][k][x]<inf){
w=f[i][j][k][x];
for(a=0;a<=A;a++){
if(sum(i+1,0,a)<sum(i+1,0,A))continue;
nj=1;
if(a==A)nj|=2;
nk=k&1;
if((j>>1)&&!(k>>1))continue;
if(a==A)nk|=(k&1)<<1;
if(x==0){
up(f[i+1][nj][nk][0],w+B+a*2);
if(a==A)up(f[i+1][nj][nk][1],w+B+A);
}
}
for(a=0;a<=A;a++){
if(sum(i+1,a,A)<sum(i+1,0,A))continue;
nj=2;
if(a==0)nj|=1;
nk=(k>>1)<<1;
if((j&1)&&!(k&1))continue;
if(a==0)nk|=k>>1;
if(x==1){
up(f[i+1][nj][nk][1],w+B+(A-a)*2);
if(a==0)up(f[i+1][nj][nk][0],w+B+A);
}
}
for(a=0;a<=A;a++)for(b=a+1;b<=A;b++){
if(sum(i+1,0,a)+sum(i+1,b,A)<sum(i+1,0,A))continue;
nj=3;
nk=k;
up(f[i+1][nj][nk][x],w+B*3+(a+A-b)*2);
nk=k&1;
if(x==0)if(!(j>>1)||(k>>1))up(f[i+1][nj][nk][0],w+B+(a+A-b)*2);
nk=(k>>1)<<1;
if(x==1)if(!(j&1)||(k&1))up(f[i+1][nj][nk][1],w+B+(a+A-b)*2);
}
up(f[i+1][3][3][x],w+B*3+A*2);
up(f[i+1][3][3][x^1],w+B*3+A);
}
ans=f[n][1][1][0];
up(ans,f[n][3][3][0]);
return printf("%d",ans),0;
}

  

最新文章

  1. 使用gulp解决RequireJS项目前端缓存问题(二)
  2. winrt 页面进入动画
  3. CSS等高布局
  4. C# 泛型简介
  5. Android 实用代码片段
  6. CSS 实现加载动画之六-大风车
  7. ubuntu下安装kde Plasma
  8. log4j使用
  9. java多线程浅谈
  10. javascript中对象的属性的特性
  11. Qt中的 Size Hints 和 Size Policies
  12. bzoj2506
  13. android 6.0获取 WRITE_SETTINGS 权限
  14. 动态获取UIWebView的真正高度
  15. ER图与UML图
  16. HDU 2087 剪花布条 KMP
  17. 利用objc的runtime来定位次线程中unrecognized selector sent to instance的问题
  18. Sonar项目主要指标以及代码坏味道详解
  19. MYCP作业
  20. 【VNC】修改VNC分辨率大小

热门文章

  1. .NoSuchBeanDefinitionException: No bean named &#39;userService&#39; available
  2. Windows10系统运行bat文件 一闪而过 解决
  3. [转] React风格的企业前端技术
  4. mysql中cast() 和convert()的用法讲解
  5. 【BZOJ4715】囚人的旋律
  6. UIActionSheet的常用方法
  7. 如何在grails2.3.x中的fork模式下进行调试?-【grails】
  8. 修改tomcat的默认访问日志信息
  9. mariadb-主主
  10. CodeForces 516C Drazil and Park 线段树