首页 > 代码库 > P1035 I need help - Smart Online Judge
P1035 I need help - Smart Online Judge
题目ID：1035
题目名称：I need help
有效耗时：31 ms
空间消耗：508 KB
程序代码：
#include<iostream>#include<vector>using namespace std;vector<int> index[10];vector<int> value[10];int f[12][12];int n,m;bool has(){ for(int i=0;i<value[n-1].size();i++){ if(value[n-1][i]==m) return true; } return false;}bool cal(){ for(int i=0;i<n;i++){ while(!index[i].empty()){ index[i].pop_back(); } while(!value[i].empty()){ value[i].pop_back(); } int min=65536; for(int j=0;j<=i;j++){ if(i==0){ index[i].push_back(j); value[i].push_back(f[i][j]); } else{ for(int k=0;k<index[i-1].size();k++){ if(index[i-1][k]==j||index[i-1][k]==j-1){ if(value[i-1][k]+f[i][j]<=m){//如果和小于m index[i].push_back(j); value[i].push_back(value[i-1][k]+f[i][j]); // cout<<value[i-1][k]+f[i][j]<<" "; } if(value[i-1][k]+f[i][j]<min){ min=value[i-1][k]+f[i][j]; } } } } }//for if(i!=0){ if(min>m){ return false; } if(index[i].size()==0) return false; } // cout<<endl; }//for return true;}int main(){ int t; cin>>t; while(t--){ cin>>n>>m; for(int i=0;i<n;i++){ for(int j=0;j<=i;j++){ int a; cin>>a; f[i][j]=a; } }//for if(cal()&&has()){ cout<<"Yes"<<endl; }else cout<<"No"<<endl; }// system("pause"); return 0;}
题目描述
Johnny Q在你的帮助下终于进入了城堡,现在出现在他面前的是一条恐怖的黑水河。河中有大量传说中的食人怪兽------法克鱿,同时还有一个N层正三角梅花桩阵,每个桩上都印有一个数字,如图所示是一个4层的正三角梅花桩阵.
Johnny Q只能从离他最近的即这个三角木桩阵的最上面一个木桩开始一个桩一个桩的跳到对岸去,每次他只能向左下或右下跳一次,跳的距离只能是一个单位步长,比如最上面的7,只能跳到3和8,而3又只能跳到4和1.跳这样的木桩对身手矫健的Johnny Q当然是小菜一碟.但是CK也不是盏省油的灯,要想跳过和还有个要求,那就是从你第一个桩跳到最后一个桩,所经过桩上的数字之和必须要等于M,否则就算跳到了最后一层的桩上,这个桩也会沉下去.比如M=21时,图中7->3->1->10是一条合法的路径,7->3->4->7也是一条合法的路径.现在你需要帮助Johnny Q判断是否存在这样的路径。
输入格式
输入的第一行是一个整数T,代表有T组测试数据.
每组测试数据的一行是两个整数N, M.其中N代表梅花桩的层数(2<=N<=10), M代表合法路径的数字和.
接下来有N行,第i行有i个数,代表这个N层梅花阵每层的数字,每个数字不会超过100.
每组测试数据的一行是两个整数N, M.其中N代表梅花桩的层数(2<=N<=10), M代表合法路径的数字和.
接下来有N行,第i行有i个数,代表这个N层梅花阵每层的数字,每个数字不会超过100.
输出格式
对于每组测试数据，输出Yes或者No，代表是否存在这样的路径。
样例输入
24 2173 84 1 57 9 10 24 1573 84 1 57 9 10 5
样例输出
YesNo
数据范围与提示
P1035 I need help - Smart Online Judge
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。