这几天一直在刷插头Dp,写了几道入门题后,觉得还比较水,直到我发现了这一题、、、、

题目大意:给你一个n*m的地图,有些是空地,有些是障碍,还有两个是ST,在给你一个L,代表可以放L个炮台,你要在空地上放炮台或者障碍,来使得S到T存在路径,喵星人会选择伤害最小的一条路径来走,你需要输出喵星人受到的最大伤害 (伤害就是指你被炮台打到的次数,炮台可以打上下左右还有斜的)

首先,很显然最后只会剩一条路径,否则就用障碍堵住就OK了

然后就变出裸裸的插头Dp了,f[k][i][j][s1][s2]代表用了k个炮台,在(i,j)这个位置,插头状态为s1,种类状态为s2,的最大伤害。 显然大多数的s2可以直接推出s1,所以状态数并不多。

因为会MLE,所以第一维要开滚动数组,具体的话看代码。

code:

//开o2
#include<cstdio>
#include<cstring>
#include<cassert>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=,maxm=;
int n,m,L,now,last,ans; char map[maxm][maxm]; bool xxx[maxm][maxm];
void init(){
scanf("%d%d%d",&n,&m,&L);
for (int i=;i<=n;++i) scanf("%s",map[i]+);
if (n<m){
for (int i=;i<=n;++i) for (int j=;j<=m;++j) if (!xxx[i][j]){
xxx[i][j]=xxx[j][i]=;
swap(map[i][j],map[j][i]);
}
swap(n,m);
}
for (int i=;i<=n;++i) for (int j=;j<=m;++j) if (map[i][j]=='T') map[i][j]='S';
}
struct Tp{int s1,s2,v;};
struct Tsp{
static const int mod=,maxm=,Index=(int)(1e9+);
int now[mod],pre[maxm],tot; Tp f[maxm];
void clear(){memset(now,,sizeof(now)); tot=;}
int find(Tp a){
int tmp=(1LL*a.s1*Index+a.s2)%mod;
for (int p=now[tmp];p;p=pre[p]) if (f[p].s1==a.s1 && f[p].s2==a.s2){
if (a.v>f[p].v) f[p].v=a.v; return f[p].v;
}
pre[++tot]=now[tmp]; now[tmp]=tot;
f[tot].s1=a.s1; f[tot].s2=a.s2; return f[tot].v=a.v;
}
}f[][][];
void addstate(int x,int y,Tp a){ // 插入进f[now][x][y]
f[now][x][y].find(a);
}
int cont1[maxn],cont2[maxn]; // cont1代表s1,cont2代表s2
// s1维护插头状态 0,1,2,3分别表示没插头,左插头,右插头,独立插头 s1还要多维护一个插头
// s2维护种类 0,1,2分别表示障碍,路径,炮台 s2还要多维护一个种类
void decode(Tp a){
for (int i=m+;i>=;--i) cont1[i]=a.s1&,a.s1>>=;
for (int i=m+;i>=;--i) cont2[i]=a.s2&,a.s2>>=;
}
Tp encode(int v){
Tp a; a.v=v; a.s1=; a.s2=;
for (int i=;i<=m+;++i) a.s1=(a.s1<<)+cont1[i];
for (int i=;i<=m+;++i) a.s2=(a.s2<<)+cont2[i];
return a;
}
int findr(int res,int x){
for (;;++x) if (cont1[x]== || cont1[x]==){
if (cont1[x]==) ++res; else --res;
if (!res) return x;
}
}
int findl(int res,int x){
for (;;--x) if (cont1[x]== || cont1[x]==){
if (cont1[x]==) ++res; else --res;
if (!res) return x;
}
}
int find(int a,int x){
if (a==) return findr(,x+);
return findl(-,x-);
}
void expand(int x,int y,Tp a){ // 不能放炮台的转移
decode(a);
int north=cont1[y],west=cont1[m+],nw=cont2[m+];
if (y== && west) return ; if (y==) nw=; cont2[m+]=cont2[y]; // 更新左上角的种类 int sum=; for (int i=;i<=m+;++i) if (cont1[i]==) ++sum; // 统计独立插头数量 int ad=; if (y> && cont2[y-]==) ++ad; if (nw==) ++ad;
if (cont2[y]==) ++ad; if (y<m && cont2[y+]==) ++ad; // 统计轮廓线上方八连通的炮台数 if (map[x][y]=='.'){ // 作为一个路径,却与起点没有关系
if ((y== || west || cont2[y-]!=) && (x== || north || cont2[y]!=)){ // 可以更新
cont2[y]=; // 更新s2
if (west && north){ // (1,2) 不可更新,否则成回路了
if (west==north){
if (west==){ // (3,3)
cont1[y]=; cont1[m+]=; addstate(x,y,encode(a.v+ad));
}
else{ // (1,1) (2,2)
cont1[find(west,y)]=west; cont1[y]=; cont1[m+]=;
addstate(x,y,encode(a.v+ad));
}
}
else if (west== || north==){ // (1,3) (2,3) (3,1) (3,2)
cont1[find(min(west,north),y)]=; cont1[y]=; cont1[m+]=;
addstate(x,y,encode(a.v+ad));
}
else if (west== && north==){ // (2,1)
cont1[y]=; cont1[m+]=; addstate(x,y,encode(a.v+ad));
}
}
else if (west && !north){ // 只能转向,不能升级成独立
cont1[y]=; cont1[m+]=west; addstate(x,y,encode(a.v+ad));
cont1[y]=west; cont1[m+]=; addstate(x,y,encode(a.v+ad));
}
else if (!west && north){ // 同上
cont1[y]=; cont1[m+]=north; addstate(x,y,encode(a.v+ad));
cont1[y]=north; cont1[m+]=; addstate(x,y,encode(a.v+ad));
}
else if (!west && !north){ // 可以变出两个左右插头,但是不能变成独立
cont1[y]=; cont1[m+]=; addstate(x,y,encode(a.v+ad));
}
}
} if (map[x][y]=='S'){ // 作为一个起点,专业生产独立插头
if ((y== || west || cont2[y-]!=) && (x== || north || cont2[y]!=)){ // 老规矩
cont2[y]=; // 虽然是起点,但也是路径
if (west && north){ // 可以滚粗了
}
if ((west && !north) || (!west && north)){
if (max(west,north)==){ // 是独立插头,合并
cont1[y]=; cont1[m+]=; addstate(x,y,encode(a.v+ad));
}
else if (sum<=){ // 不是独立插头,将其升级为独立插头
cont1[find(max(west,north),y)]=;
cont1[y]=; cont1[m+]=; addstate(x,y,encode(a.v+ad));
}
}
if (!west && !north && sum<=){ // 没有插头,那就直接产生一个
cont1[y]=; cont1[m+]=; addstate(x,y,encode(a.v+ad));
cont1[y]=; cont1[m+]=; addstate(x,y,encode(a.v+ad));
}
}
} if (map[x][y]!='S'){ // 不是起点大哥,就可以放障碍啦~
if (!west && !north){ // 当然要没有插头才可以放障碍
if (map[x][y]=='.') decode(a),cont2[m+]=cont2[y];
cont2[y]=; cont1[y]=; cont1[m+]=; addstate(x,y,encode(a.v));
}
}
}
void expand_pt(int x,int y,Tp a){ // 只能放炮台
decode(a);
int north=cont1[y],west=cont1[m+],nw=cont2[m+];
if (north || west || map[x][y]!='.') return; if (y==) nw=; int ad=; if (y> && cont2[y-]==) ++ad; if (nw==) ++ad;
if (cont2[y]==) ++ad; if (y<m && cont2[y+]==) ++ad; // 统计路径个数 cont2[m+]=cont2[y]; cont2[y]=; addstate(x,y,encode(a.v+ad));
}
void clearf(int x){
for (int i=;i<=n;++i) for (int j=;j<=m;++j) f[x][i][j].clear();
}
void work(){
now=,last=; clearf(now); Tsp *x;
for (int l=;l<=L;++l){ // now->l , last->l-1
addstate(,,(Tp){,,}); x=&f[now][][]; // l更新l now->now
for (int i=;i<=n;++i) for (int j=;j<=m;++j){ // x是上一个
for (int k=;k<=x->tot;++k) expand(i,j,x->f[k]);
x=&f[now][i][j];
}
swap(now,last); clearf(now); // now->l+1 , last=l
if (l!=L){
x=&f[last][][];
for (int i=;i<=n;++i) for (int j=;j<=m;++j){
for (int k=;k<=x->tot;++k) expand_pt(i,j,x->f[k]);
x=&f[last][i][j];
}
}
for (int k=;k<=x->tot;++k)
if (x->f[k].s1== && x->f[k].v>ans) ans=x->f[k].v;
}
printf("%d\n",ans);
}
int main(){
init();
work();
return ;
}

最新文章

  1. 标题栏Menu
  2. Java基础知识笔记(四:多线程基础及生命周期)
  3. ChannelPipeline
  4. Table的行列合并
  5. 一款可以下拉搜索html下拉框控件
  6. JavaSE配置文件java.util.Properties【单例模式Singleton】
  7. 使用STL map 用 string 做索引 插入删除数据
  8. 【Tsinghua OJ】灯塔(LightHouse)问题
  9. PDM文件编辑
  10. C++ 实现网络爬虫
  11. spring aop原理分析
  12. softlayerFastUploadVHDtoBS
  13. js document
  14. python之路: 线程、进程和协程
  15. pytorch实现DCGAN、pix2pix、DiscoGAN、CycleGAN、BEGAN以及VAE
  16. centos7系列Cobbler+kickstart全自动装机实战
  17. 英语演讲稿——Get Along with Fear
  18. js代码实现购物车效果
  19. J05-Java IO流总结五 《 BufferedInputStream和BufferedOutputStream 》
  20. 火狐浏览器Firefox如何使用插件,火狐有哪些好用的插件

热门文章

  1. C++笔试题(十)
  2. Django学习:url路由系统
  3. 如何访问google?
  4. python之类的相关名词-继承-
  5. [Usaco2012 Jan]Video Game
  6. 题解报告:NYOJ #737 石子合并(一)(区间dp)
  7. 题解报告:hdu 2141 Can you find it?(二分)
  8. (027)[技术资料]业余制作Windows图标
  9. C#基础学习1
  10. PHP设计模式 原型模式(Prototype)