搜索，动规 经典题目体验赛总结
T1 工作依赖
题目
题目描述(Description):
2008年，奥运会将在中国举行。众所周知举办奥运会是一个庞大的工程，有许多准备工作要做，而这些工作也是要分先后、存在依赖关系的。比如我们说工作2依赖于工作1，意思是说在工作2开始做之前要必须结束工作1。我们假设，在一个时刻只有一个工作在进行，而且每样工作所依赖的其它工作不会超过10个。
输入文件:
第一行有两个整数N（0<=N<=10000）和M。所有工作从1到N编号。你需要计算第M个工作的最早结束时间。
接下来N行每行描述一个工作，第1行描述工作1，第二行描述工作2，……，以此类推。每行包含几个正整数，第i行的第1个整数是完成第i个工作需要的时间T（0<T<=100），第i行的其余数字是第i个工作所依赖的其它工作编号。我们保证不会出现循环依赖。
输出文件:
一个整数：工作M的最早结束时间。
样例(Sample):
Sample Input Case 1:
2 2
3
2 1
Sample Output Case 1:
5
Sample Input Case 2:
3 3
3
2 1
4 1 2
Sample Output Case 2:
9
分析
有依赖性……深搜，广搜都行，别忘了染色（防重复）
最坑人的是读入；题目没说每行多少个，每行末尾又不一定有回车，于是，标程爆零……而我，很不幸，在下发标程后发现自己的读入方法跟标程差不多，于是——我跟标程一起爆零了
我心伤悲，莫知我哀
代码
深搜：（核心代码）
int dfs(int u)
{
if(vis[u]) return 0;
if(f[u]) return f[u];
for(int i=1;i<=depend[u];i++) {
int v=works[u][i];
f[u]+=dfs(v);
visit[v]=1;
}
return f[u]+cost[u];
}
广搜：
我的代码：
/*
User:Mandy.H.Y
Language:c++
Problem:work
*/
#include<bits/stdc++.h>
#define Max(x,y) (x)>(y)?(x):(y)
#define Min(x,y) (x)<(y)?(x):(y)
#define mem(A) memset((A),0,sizeof(A))
using namespace std;
const int maxn=10005;
int n,m,ans;
int t[maxn],a[maxn][12];
bool vis[maxn];
queue<int>q;
template<typename T>inline int read(T &x)
{
x=0;char c=getchar();bool f=0;
while(c<'0'||c>'9') {f|=(c=='-');c=getchar();}
while(c>='0'&&c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
if(f)x=-x;
}
template<typename T>void putch(const T x)
{
if(x>9) putch(x/10);
putchar((x%10)|48);
}
template<typename T>inline void put(const T x)
{
if(x<0) putchar('-'),putch(-x);
else putch(x);
}
void docu()
{
freopen("work.txt","r",stdin);
}
void readdata()
{
read(n);
read(m);
char c;
for(int i=1;i<=n;++i)
{
scanf("%d",&t[i]);
int j=0;
c=getchar();
while(c!='\n')
{
if(c>='0'&&c<='9')
{
++j;
while(c>='0'&&c<='9')
{
a[i][j]=(a[i][j]<<3)+(a[i][j]<<1)+(c^48);
c=getchar();
}
}
else c=getchar();
}
/*
emmmmm,以下写法要超时QAQ
考场就因为这个爆零
而且据说标程与这个写法类似
所以……标程爆零了……
c=getchar();
while(c!='\n')
{
scanf("%d",&a[i][++j]);
c=getchar();
}
*/
}
}
void bfs()
{
while(!q.empty())
{
int u=q.front();
q.pop();
ans+=t[u];
if(!a[u][1]) continue;
for(int i=1;a[u][i];++i)
{
if(!vis[a[u][i]])
{
q.push(a[u][i]);
vis[a[u][i]]=1;
}
}
}
}
void work()
{
q.push(m);
vis[m]=1;
bfs();
put(ans);
}
int main()
{
// docu();
readdata();
work();
return 0;
}
T2 英雄
题目
题目描述(Description):
城堡迷宫由N×M个格子组成，英雄Mario玛丽奥要在城堡迷宫中从起始点移动到目标点去拯救被怪物掳去的公主，他每一步只能从当前所在的格子移动到相邻的4个格子之一，而且不能移出城堡的范围，走一步需要1秒的时间。
城堡中某些格子里面有弹簧，每个弹簧具有特定的能量K，不同弹簧的K值不一定相同。如果Mario跳到一个有弹簧的格子，他就会继续向前跳K个格子或者被墙所阻挡无法继续向前，这个时间忽略不计。
请你计算Mario从起始点到达目标点（公主位置）需要的最短时间，如果不能到达，输出“Impossible”。
输入文件:
第一行，两个整数，N和M（3<=N,M<=100），分别表示城堡的行和列。
第二行，一个非负整数K，表示弹簧的数量。接下来K行，每行含3个正整数——X，Y，P。其中X，Y是弹簧的坐标（2<=X<=N-1，2<=Y<=M-1），P是该弹簧的能量。
接下来最后两行，第一行是Mario的坐标，第二行是公主的坐标。
注意：输入文件保证没有一个弹簧是挨着城堡围墙的。
输出文件(hero.out):
输出Mario从初始位置到达公主所在位置需要的最短时间（秒）。
如果不能到达，则输出“Impossible”。（引号不需输出）
样例(Sample):
Sample Input Case 1:
10 10
1
2 7 5
2 8
1 1
Sample Output Case 1:
3
分析
裸的广搜，不过多了个弹簧，可恶的是，弹簧可以连跳所以是while不是if
沈大佬用深搜A了这道题，膜拜大佬中……
代码
深搜：（感谢沈大佬）
#include<bits/stdc++.h>
#define maxn 110
#define inf 0x3f3f3f3f
using namespace std;
int m,n,k,mp[maxn][maxn],ans=inf,bj[maxn][maxn],qdx,qdy,zdx,zdy;
void dfs(int x,int y,int cost){
if(cost>ans) return;
if(x==zdx&y==zdy) {ans=cost;return;}
bj[x][y]=cost;
if(x+1<=n) {//shang
int i=x+1,j=y;
while(mp[i][j]){
i=min(n,i+mp[i][j]);
}
if(cost+1<bj[i][j]) dfs(i,j,cost+1);
}
if(x-1>=1){//xia
int i=x-1,j=y;
while(mp[i][j]){
i=max(1,i-mp[i][j]);
}
if(cost+1<bj[i][j]) dfs(i,j,cost+1);
}
if(y-1>=1){//zuo
int i=x,j=y-1;
while(mp[i][j]){
j=max(1,j-mp[i][j]);
}
if(cost+1<bj[i][j]) dfs(i,j,cost+1);
}
if(y+1<=m){//you
int i=x,j=y+1;
while(mp[i][j]){
j=min(m,j+mp[i][j]);
}
if(cost+1<bj[i][j]) dfs(i,j,cost+1);
}
return;
}
int main(){
memset(bj,inf,sizeof(bj));
scanf("%d%d",&n,&m);
scanf("%d",&k);
for(int i=1;i<=k;i++){
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
mp[x][y]=z;
}
scanf("%d%d",&qdx,&qdy);
scanf("%d%d",&zdx,&zdy);
dfs(qdx,qdy,0);
if(ans==inf) printf("Impossible\n");
else printf("%d\n",ans);
return 0;
}
广搜：
/*
User:Mandy.H.Y
Language:c++
Problem:hero
*/
#include<bits/stdc++.h>
#define Max(x,y) (x)>(y)?(x):(y)
#define Min(x,y) (x)<(y)?(x):(y)
#define mem(A) memset((A),0,sizeof(A))
using namespace std;
const int maxn=105;
struct zb
{
int x,y;
};
int n,m,k,xm,ym,xp,yp;
int jump[100][100];
int vis[102][102];
queue<zb>q;
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
template<typename T>inline void read(T &x)
{
x=0;char c=getchar();bool f=0;
while(c<'0'||c>'9') {f|=(c=='-');c=getchar();}
while(c>='0'&&c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
if(f)x=-x;
}
template<typename T>void putch(const T x)
{
if(x>9) putch(x/10);
putchar((x%10)|48);
}
template<typename T>inline void put(const T x)
{
if(x<0) putchar('-'),putch(-x);
else putch(x);
}
void docu()
{
freopen("hero.txt","r",stdin);
}
void readdata()
{
read(n); read(m); read(k);
for(int i=1;i<=k;++i)
{
int x,y;
read(x); read(y);
read(jump[x][y]);
}
read(xm); read(ym);
read(xp); read(yp);
}
bool bfs()
{
while(!q.empty())
{
zb u=q.front();
q.pop();
for(int i=0;i<4;++i)
{
int nx=u.x+dx[i];
int ny=u.y+dy[i];
if(nx<1||nx>n||ny<1||ny>m) continue;//是N*M的地图不是N*N
if(vis[nx][ny]) continue;
if(jump[nx][ny]==0)
{
vis[nx][ny]=vis[u.x][u.y]+1;
if(nx==xp&&ny==yp) return 1;
zb v; v.x=nx; v.y=ny;
q.push(v);
}
else
{
int xx,yy;
while(jump[nx][ny])//注意要连跳
{
xx=Min(Max(nx+dx[i]*jump[nx][ny],1),n);
yy=Min(Max(ny+dy[i]*jump[nx][ny],1),m);//连跳只能向一个方向
nx=xx; ny=yy;
if(xx==xp&&yy==yp)
{
vis[xx][yy]=vis[u.x][u.y]+1;
if(xx==xp&&yy==yp) return 1;
}
}
// mem(vis1);
if(vis[xx][yy]) continue;
vis[xx][yy]=vis[u.x][u.y]+1;
if(xx==xp&&yy==yp) return 1;
zb v; v.x=xx; v.y=yy;
q.push(v);
}
}
}
return 0;
}
void work()
{
zb u; u.x=xm; u.y=ym;
q.push(u);
vis[xm][ym]=1;
if(xm==xp&&ym==yp)
{
put(0);
return;
}
if(bfs()) put(vis[xp][yp]-1);//记住减一
else printf("Impossible");
}
int main()
{
// docu();
readdata();
work();
return 0;
}
T3 不老的传说
题目
题目描述(Description):
一位先知告诉Ddynamic，在遥远的地方，有一处不老的泉水，在那里，他可以找到他人生的意义。按照先知的指引，Dynamic出发了。翻越雪山，穿过丛林，度过汪洋，终于来到了沙漠的深处。按照先知的说法，泉水就在这个地方。然而除了无尽的沙漠之外，什么都没有。
Dynamic几乎绝望了，他盲目地走着，突然来到了一圈奇异的巨石前，在巨石阵的中央清晰地传来泉水轻快的声音。巨大的石头挡住了去路，Dynamic无法前进了。突然间，本来无色的石头闪烁出绚丽夺目的光芒，与泉水声交织成诗一般的乐章。然后一刹那间，色彩消失了。
“这里面一定又什么秘密，我要把石头染成刚才的颜色！”Dynamic对自己说，他还清楚地记得每一块石头的颜色。智慧女神雅典娜这时出现了，递给他一把神奇的刷子，说“这把刷子每次可以把连续的不超过K块石头刷成一种新颜色，新刷的颜色会覆盖原来的颜色。用最少的次数，恢复石阵的光彩，你就会找到不老的泉水。”
Dynamic意识到这并不是一件容易的事，他出发得太匆忙，忘了带上手提电脑。你能帮助他吗？
输入文件:
第1行包含3个整数N，C，K。其中N是石头的个数，C是颜色的种类，K是每次最多刷过的石头的个数。1≤N≤200，1≤C，K≤N 。
第2行包含N个整数，分别是N块石头最终的颜色，按照顺时针的顺序。颜色是1到C之间的一个整数，整数之间用一个空格隔开。开始的时候，所有的石头都是无色的。
输出文件:
输出一个整数，为需要的最少次数。
样例(Sample):
Sample Input Case 1:
5 2 3
1 2 1 2 1
Sample Output Case 1:
3
分析
很经典的区间动规
我们以dp[i][j] 表示从 i 到 j 的区间的最少涂色次数
枚举 l 为区间 [i,j] 中的一块石头如果 l 需要被染成的颜色与 i 一样，且他们可以同时被涂色，则dp[i][j]=min(dp[i][j],dp[i+1][l]+dp[l+1][j])
代码
/*
User:Mandy.H.Y
Language:c++
Problem:spring
*/
#include<bits/stdc++.h>
#define Max(x,y) (x)>(y)?(x):(y)
#define Min(x,y) (x)<(y)?(x):(y)
#define mem(A) memset((A),0,sizeof(A))
using namespace std;
const int maxn=205;
int n,C,k,ans;
int a[maxn<<1],dp[maxn<<1][maxn<<1];
template<typename T>inline void read(T &x)
{
x=0;char c=getchar();bool f=0;
while(c<'0'||c>'9') {f|=(c=='-');c=getchar();}
while(c>='0'&&c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
if(f)x=-x;
}
template<typename T>void putch(const T x)
{
if(x>9) putch(x/10);
putchar((x%10)|48);
}
template<typename T>inline void put(const T x)
{
if(x<0) putchar('-'),putch(-x);
else putch(x);
}
void docu()
{
freopen("spring.txt","r",stdin);
}
void readdata()
{
read(n);
read(C);
read(k);
for(int i=1;i<=n;++i)
{
read(a[i]);
a[i+n]=a[i];//环形开二倍
}
}
void work()
{
int n2=n<<1;
for(int i=1;i<=n2;++i) dp[i][i]=1;//初始化
for(int i=n2-1;i>0;--i)
{
for(int j=i+1;j<=n2;++j)
{
dp[i][j]=dp[i+1][j]+1;//实时更新dp[i][j] ，也算赋初值
for(int l=i+1;l<=j;++l)//l<=j 若l==j又满足 a[i]==a[l]&&l-i+1<=k，则dp[i][j]可能等于dp[i+1][j];
{
if(a[i]==a[l]&&l-i+1<=k)//l-i+1<=k
{
dp[i][j]=Min(dp[i][j],dp[i+1][l]+dp[l+1][j]);
//至于为何是dp[i+1][l],因为i与l可以被同时涂色啊
}
}
}
}
ans=0x3f3f3f3f;
for(int i=1;i<=n;++i)
{
ans=Min(ans,dp[i][i+n-1]);//i+n-1
}
put(ans);
}
int main()
{
// docu();
readdata();
work();
return 0;
}