网站建设用阿里还是华为云,wordpress主题cms博客,网站备案行业,昆明seo题干#xff1a;
Help Jimmy 是在下图所示的场景上完成的游戏。 场景中包括多个长度和高度各不相同的平台。地面是最低的平台#xff0c;高度为零#xff0c;长度无限。 Jimmy老鼠在时刻0从高于所有平台的某处开始下落#xff0c;它的下落速度始终为1米/秒。当Jim…题干
Help Jimmy 是在下图所示的场景上完成的游戏。 场景中包括多个长度和高度各不相同的平台。地面是最低的平台高度为零长度无限。 Jimmy老鼠在时刻0从高于所有平台的某处开始下落它的下落速度始终为1米/秒。当Jimmy落到某个平台上时游戏者选择让它向左还是向右跑它跑动的速度也是1米/秒。当Jimmy跑到平台的边缘时开始继续下落。Jimmy每次下落的高度不能超过MAX米不然就会摔死游戏也会结束。 设计一个程序计算Jimmy到底地面时可能的最早时间。
Input
第一行是测试数据的组数t0 t 20。每组测试数据的第一行是四个整数NXYMAX用空格分隔。N是平台的数目不包括地面X和Y是Jimmy开始下落的位置的横竖坐标MAX是一次下落的最大高度。接下来的N行每行描述一个平台包括三个整数X1[i]X2[i]和H[i]。H[i]表示平台的高度X1[i]和X2[i]表示平台左右端点的横坐标。1 N 1000-20000 X, X1[i], X2[i] 200000 H[i] Y 20000i 1..N。所有坐标的单位都是米。 Jimmy的大小和平台的厚度均忽略不计。如果Jimmy恰好落在某个平台的边缘被视为落在平台上。所有的平台均不重叠或相连。测试数据保证问题一定有解。
Output
对输入的每组测试数据输出一个整数Jimmy到底地面时可能的最早时间。 AC代码1
#includecstdio
#includealgorithm
#includeiostream
#includecstring
using namespace std;
const int INF 0x3f3f3f3f;
int n,x,y,maxx;
int dp[1005][2];//fg0代表左边fg1代表右边
struct Node {int l,r,h;
} node[1005];
bool cmp(const Node a,const Node b) {return a.h b.h;
}
int dfs(int cur,int fg) {if(cur 1) return 0;if(dp[cur][fg] ! -1) return dp[cur][fg];if(cur 1) {return 0;}int ans INF;if(dp[cur][fg] ! -1) {return dp[cur][fg];}int temp cur; for(int i cur-1; i1; i--) {tempi;if(node[cur].h - node[i].h maxx) break;if(fg0) {if(node[i].l node[cur].l node[i].r node[cur].l) {ans min(dfs(i,0)node[cur].l-node[i].l,dfs(i,1) node[i].r-node[cur].l );break;}} else {if(node[i].r node[cur].r node[i].l node[cur].r) {ans min(dfs(i,0)node[cur].r-node[i].l,dfs(i,1)node[i].r-node[cur].r);break;}}}if(ans INF) {if(node[cur].h maxx) return dp[cur][fg] 0;else return dp[cur][fg] ans;}else return dp[cur][fg] ans;
}
int main()
{int t;cint;while(t--) {scanf(%d%d%d%d,n,x,y,maxx);memset(dp,-1,sizeof (dp));for(int i 1; in; i) {scanf(%d%d%d,node[i].l,node[i].r,node[i].h);}sort(node1,noden1,cmp);int okn1;
// node[ok].h y;node[ok].lnode[ok].rx;for(int i n; i1; i--) {if(node[i].r x node[i].l x) {oki;break;}}if(ok n1) {printf(%d\n,y);}else {int ans min(dfs(ok,1) node[ok].r-x,dfs(ok,0) x-node[ok].l) y;
// int ans min(dfs(ok,1),dfs(ok,0)) y;printf(%d\n,ans);}} return 0 ;}
//1
//1
//2 3
//100
//5 6 1
AC代码2
#includecstdio
#includealgorithm
#includeiostream
#includecstring
using namespace std;
const int INF 0x3f3f3f3f;
int n,x,y,maxx;
int dp[1005][2];//fg0代表左边fg1代表右边
struct Node {int l,r,h;
} node[1005];
bool cmp(const Node a,const Node b) {return a.h b.h;
}
int dfs(int cur,int fg) {if(cur 1) return 0;if(dp[cur][fg] ! -1) return dp[cur][fg];
// int minn 0x3f3f3f3f,flag0;//0左 1右
// int tempcur;int ans INF;int temp cur; for(int i cur-1; i1; i--) {tempi;if(node[cur].h - node[i].h maxx) break;if(fg0) {if(node[i].l node[cur].l node[i].r node[cur].l) {ans min(dfs(i,0)node[cur].l-node[i].l,dfs(i,1) node[i].r-node[cur].l );break;}} else {if(node[i].r node[cur].r node[i].l node[cur].r) {ans min(dfs(i,0)node[cur].r-node[i].l,dfs(i,1)node[i].r-node[cur].r);break;}}}if(ans INF) {if(node[cur].h maxx) return dp[cur][fg] 0;else return dp[cur][fg] ans;}else return dp[cur][fg] ans;
// if(ans INF) {
// if(temp 1) {
// if(node[cur].h maxx) return dp[cur][fg] ans;
// else return dp[cur][fg] 0;
// }
// return dp[cur][fg] ans;
// }
// else return dp[cur][fg] ans;
}
int main()
{int t;cint;while(t--) {scanf(%d%d%d%d,n,x,y,maxx);memset(dp,-1,sizeof (dp));for(int i 1; in; i) {scanf(%d%d%d,node[i].l,node[i].r,node[i].h);}sort(node1,noden1,cmp);int okn1;node[ok].h y;node[ok].lnode[ok].rx;
// for(int i n; i1; i--) {
// if(node[i].r x node[i].l x) {
// oki;break;
// }
// }
// int ans min(dfs(ok,1) node[ok].r-x,dfs(ok,0) x-node[ok].l) y;int ans min(dfs(ok,1),dfs(ok,0)) y;printf(%d\n,ans);} return 0 ;}
错误代码
#includecstdio
#includealgorithm
#includeiostream
#includecstring
using namespace std;
int n,x,y,maxx;
int dp[1005];
struct Node {int l,r,h;
} node[1005];
bool cmp(const Node a,const Node b) {return a.h b.h;
}
int dfs(int cur,int curx,int curh) {if(curh 0) return 0;if(cur 0) return 0;if(dp[cur] ! -1) return dp[cur];int minn 0x3f3f3f3f;for(int i cur-1; i1; i--) {if(curh - node[i].h maxx) break;if(node[i].l node[cur].l) minn min(minn,dfs(i,node[cur].l,node[i].h)node[cur].l-curx);if(node[i].r node[cur].r) minn min(minn,dfs(i,node[cur].r,node[i].h)node[cur].r-curx);}return dp[cur] minn;
}
int main()
{int t;cint;while(t--) {scanf(%d%d%d%d,n,x,y,maxx);memset(dp,-1,sizeof (dp));for(int i 1; in; i) {scanf(%d%d%d,node[i].l,node[i].r,node[i].h);}sort(node1,noden1,cmp);printf(%d\n,dfs(n,x,node[n].h));}
// 18653293769return 0 ;}
总结 几个地方是真的坑首先这个错误代码记忆化搜素的设计状态我就没搞明白因为后来我通过观察发现一维dp表示不了所有状态于是dfs中乱设了一堆参数结果显然都没用。 其二函数内部显然要break不能不加break因为有上一个台子挡住了后面即使有符合的也不能跳上去了所以要break。 其三要处理好到地面的那一步一定是直接跳过去的也就是 一定ansINF所以return的时候不能直接retrun dp[cur][fg] ans;而应该判断是否ansINF 如果等于的话也就说明是到地面了要dp[cur][fg] 0;才可以。 其四有个处理技巧让出发点当成一个新的平台这样直接统一形式就可以了。不然的话就跟AC代码1一样先判断是否从出发点可以直接落到地面上特判一下这个条件才可以。 其五有个技巧就是高度都最后统一算直接y就可以了这样减少了代码出错概率。 其六递归函数中的状态转移要想清楚到底是由哪些状态转移而来或者想可以转移到哪些状态去。
