概述
Problem B:Jump
Time Limit:1000MS Memory Limit:65536K
Total Submit:43 Accepted:12 Page View:297
[Submit] [Status] [Clarify]
Font Size:
Aa
Aa
Aa
Description
There is n pillars, their heights are (A1,A2,A3,…An. You can jump at the top of the pillars. But you will lose abs(a[j]-a[i])*abs(j-i) power when you jump from i-th pillar to j-th pillar. At first you have m power. Can you jump from s-th pillar to e-th pillar?
Input
The input consists of several test cases.
Every test case is two integer n(2<=n<200), q(1=
The second line contain n integer A1, A2, A3,..An.
The next q line contain there integer s, e, m .
Output
If you can jump from s to e, with less or equal m power output “Yes”, else output “No”
Sample Input
3 3
1 2 3
1 3 2
1 2 1
1 3 1
Sample Output
Yes
Yes
No
Hint
Abs(a-b) mean the absolute value of a-b.
最短路问题,floyd算法!
#include <iostream>
using namespace std;
#define N 205
int f(int x)
return x>=0?x:-x;
}
int main()
{
int n,q,map[N][N];
while(cin>>n>>q)
{
int i, j, k;
int a[N];
for(i=0;i<n;i++)
cin>>a[i];
for(i=0; i<n; i++)
for(j=0; j<n; j++)
map[i][j] = f(a[i]-a[j])*f(i-j);
for(k=0; k<n; k++)
for(i=0; i<n; i++)
for(j=0; j<n; j++)
if(map[i][k]+map[k][j]<map[i][j])
map[i][j] = map[i][k]+map[k][j];
while(q--)
{
int s, e, m;
cin>>s>>e>>m;
if(map[s-1][e-1]<=m)
cout<<"Yes"<<endl;
else
cout<<"No"<<endl;
}
}
return 0;
}
{
最后
以上就是懵懂黄蜂为你收集整理的Jump的全部内容,希望文章能够帮你解决Jump所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错,欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
发表评论 取消回复