传送门:http://acm.hdu.edu.cn/showproblem.php?pid=3681
题意:
一个机器人想越狱,他只能带一定电量的电池,'S'表示道路可行,'G'表示充电器,只可充电一次,但是可以经过很多次。'F'表示起点,'Y'表示要破坏的机关,也是只能破坏一次,但是可以经过无数次。'D'表示不能经过的地点。求他能破坏所有机关,带的最小初始电量。
题解:
一看就知道是IDA*搜索,然后果断TLE了,最后看别人的代码,才知道是Dp+状态压缩。
开始的时候预处理每个YGF之间的最短距离,然后二分答案,每次用dp路径问题求解是否越狱。
AC代码:
Accepted |
3681 |
640MS |
9100K |
3847 B |
G++ |
XH_Reventon |
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <list>
#include <deque>
#include <queue>
#include <iterator>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <cctype>
using namespace std;
#define si1(a) scanf("%d",&a)
#define si2(a,b) scanf("%d%d",&a,&b)
#define sd1(a) scanf("%lf",&a)
#define sd2(a,b) scanf("%lf%lf",&a,&b)
#define ss1(s) scanf("%s",s)
#define pi1(a) printf("%d\n",a)
#define pi2(a,b) printf("%d %d\n",a,b)
#define mset(a,b) memset(a,b,sizeof(a))
#define forb(i,a,b) for(int i=a;i<b;i++)
#define ford(i,a,b) for(int i=a;i<=b;i++)
typedef long long LL;
const int N=33;
const int INF=0x3f3f3f3f;
const double PI=acos(-1.0);
const double eps=1e-8;
int n,m;
int cnt,ac,fid;
char mp[20][20];
int dis[20][20];
int dp[1<<17][17];
int nd[20][2];
int dir[4][2]={1,0, -1,0, 0,1, 0,-1};
struct xh
{
int x,y;
}w,e;
int bfs(int x,int y,int xx,int yy)
{
queue<xh> q;
int vd[20][20];
mset(vd,-1);
if(xx==x&&yy==y) return 0;
w.x=x; w.y=y;
q.push(w);
vd[x][y]=0;
while(!q.empty())
{
e=q.front();
q.pop();
for(int i=0;i<4;i++)
{
w.x=e.x+dir[i][0];
w.y=e.y+dir[i][1];
if(w.x<0||w.x>=n||w.y<0||w.y>=m) continue;
if(mp[w.x][w.y]=='D'||vd[w.x][w.y]!=-1) continue;
vd[w.x][w.y]=vd[e.x][e.y]+1;
q.push(w);
if(w.x==xx&&w.y==yy) return vd[w.x][w.y];
}
}
return -1;
}
void xiaohao_dp()
{
for(int i=0;i<cnt;i++)
for(int j=i;j<cnt;j++)
{
if(i==j) dis[i][j]=0;
else
dis[j][i]=dis[i][j]=bfs(nd[i][0],nd[i][1],nd[j][0],nd[j][1]);
}
}
bool check(int gg)
{
mset(dp,-1);
dp[1<<fid][fid]=gg;
int ans=-1;
for(int i=0;i<(1<<cnt);i++)
for(int j=0;j<cnt;j++)
{
if((i&(1<<j))==0)continue;
if((i&(ac))==ac)
if(dp[i][j]!=-1)
return true;
for(int k=0;k<cnt;k++)
{
if(dp[i][j]==-1||k==j||(i&(1<<k))||dis[j][k]==-1)continue;
int tem=dp[i][j]-dis[j][k];
if(tem<0)continue;
dp[i+(1<<k)][k]=max(dp[i+(1<<k)][k],tem);
if(mp[nd[k][0]][nd[k][1]]=='G') dp[i+(1<<k)][k]=gg;
}
}
return false;
}
int main()
{
// freopen("input.txt","r",stdin);
while(si2(n,m)&&(n+m))
{
for(int i=0;i<n;i++)
scanf("%s",mp[i]);
cnt=ac=0;
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
{
if(mp[i][j]=='D'||mp[i][j]=='S') continue;
if(mp[i][j]=='Y')
{
nd[cnt][0]=i,nd[cnt][1]=j;
ac+=1<<cnt;
}
if(mp[i][j]=='G')
{
nd[cnt][0]=i,nd[cnt][1]=j;
}
if(mp[i][j]=='F')
{
fid=cnt;
nd[cnt][0]=i,nd[cnt][1]=j;
ac+=1<<cnt;
}
cnt++;
}
xiaohao_dp();//预处理每个YGF之间的最短距离
int l=0,r=30,m;
int ans=1<<30;
while(l<=r)//二分
{
m=(l+r)>>1;
if(check(m))
{
r=m-1;
ans=min(ans,m);
}
else
l=m+1;
}
if(ans==(1<<30))
puts("-1");
else
printf("%d\n",ans);
}
return 0;
}
这是开始的思路,看见题目问最小的电池容量为多少,就想到了IDA*,刚好是处理这个状态不好表示的问题,然后就果断TLE了。
TLE代码:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <list>
#include <deque>
#include <queue>
#include <iterator>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <cctype>
using namespace std;
#define si1(a) scanf("%d",&a)
#define si2(a,b) scanf("%d%d",&a,&b)
#define sd1(a) scanf("%lf",&a)
#define sd2(a,b) scanf("%lf%lf",&a,&b)
#define ss1(s) scanf("%s",s)
#define pi1(a) printf("%d\n",a)
#define pi2(a,b) printf("%d %d\n",a,b)
#define mset(a,b) memset(a,b,sizeof(a))
#define forb(i,a,b) for(int i=a;i<b;i++)
#define ford(i,a,b) for(int i=a;i<=b;i++)
typedef long long LL;
const int N=33;
const int INF=0x3f3f3f3f;
const double PI=acos(-1.0);
const double eps=1e-8;
int n,m,yY,full;
int bx,by;//开始位置
char mp[20][20];
char xh[20][20];
bool flag,vis[400][20][20];
int dir[4][2]={1,0, -1,0, 0,1, 0,-1};
//k代表已经拿到了几个Y,depth代表剩下的电力
void dfs(int x,int y,int k,int depth)
{
if(!flag) return ;
if(k==yY){flag=false; return ;}
if(depth==0) return ;
for(int i=0;i<4;i++)
{
int xx=x+dir[i][0];
int yy=y+dir[i][1];
if(xx<0||xx>=n||yy<0||yy>=m) continue;
if(xh[xx][yy]=='D') continue;
if(xh[xx][yy]=='S')
{
if(vis[k][xx][yy]) continue;
vis[k][xx][yy]=1;
dfs(xx,yy,k,depth-1); if(!flag) return ;
vis[k][xx][yy]=0;
}
if(xh[xx][yy]=='G')
{
xh[xx][yy]='S';
vis[k][xx][yy]=1;
dfs(xx,yy,k,full); if(!flag) return ;
vis[k][xx][yy]=0;
xh[xx][yy]='G';
}
if(xh[xx][yy]=='Y')
{
xh[xx][yy]='S';
vis[k+1][xx][yy]=1;
dfs(xx,yy,k+1,depth-1); if(!flag) return ;
vis[k+1][xx][yy]=0;
xh[xx][yy]='Y';
}
}
}
void IDA()
{
if(yY==0)
{
puts("0");
return ;
}
flag=true;
int depth=0;
while(flag)
{
for(int i=0;i<n;i++)
strcpy(xh[i],mp[i]);
mset(vis,0);
depth++;
if(depth>=15) break;
vis[0][bx][by]=1; xh[bx][by]='S';
full=depth;
dfs(bx,by,0,depth);
}
if(flag) puts("-1");
else printf("%d\n",depth);
}
int main()
{
// freopen("input.txt","r",stdin);
while(si2(n,m)&&(n+m))
{
for(int i=0;i<n;i++)
scanf("%s",mp[i]);
yY=0;
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
{
if(mp[i][j]=='Y')
yY++;
if(mp[i][j]=='F')
bx=i,by=j;
}
IDA();
}
return 0;
}
分享到:
相关推荐
hdu 3341(ac自动机+状态压缩) 题意:容易理解... 思路:首先一开始容易想到要用到dp,开设一个dp[41][41][41][41][501]的数组来解决,但是明显内存已经超出范围了,于是就想如何减少内存呢?只要知道A、T、C、G其中...
ACM题库,一些题目和答案,以及解题报告,传上来共享
杭电OnlineJudge 200-2099的解题报告
acm hdu as easy as a+b
HDU的一题........HDU DP动态规
hdu 1695 GCD(欧拉函数+容斥原理).docx
本人准备2020年保研机试时刷的题目(虽然最后机试取消了,...来自某中流985,在HDU和vjudge平台上大概刷了400道。本文件地图(excel表格)包含了绝大部分我刷过的题目,笔记中具有思路、代码、总结和心得。 大佬勿入!
动态规划(dynamic programming)是运筹学的一个分支,是求解决策过程(decision process)最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时,...
Problem Description 话说,经过了漫长的一个多月,小明已经成长了许多,所以他改了一个名字叫“大明”。 这时他已经不是那个只会做100以内加法的那个“小明”了,现在他甚至会任意长度的正小数的加法。...
HDU上DP大集合,里面包括题,题解,代码,对DP入门者很实用,对DP老手也是有很大的提高
从简单入门到偏中等的几个题,线段树很灵活,主要懂了lazy操作,其他的自己yy吧。
300+ AC 代码 。 大数 , 线段树 , 字符串 , dp.....
动态规划DP题解 POJ HDU部分动态规划DP题解
acm入门之枚举搜索,学校第一次acm培训,包括枚举及其优化,dfs和bfs
hdu 1005.比较简单的一道题,有兴趣的可以看看。
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
2、new做两件事,一是分配内存,二是调用类的构造函数 3、new建立的是一个对象,而malloc分配的是一块内存 4、new/delete是保留字,不需要头文
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
HDU1059的代码
杭电ACMhdu1163