问题 BJ: 数字三角形2
内存限制：128 MB
时间限制：1.000 S
标准输入输出
题目类型：传统
评测方式：文本比较
上传者：admin
提交：128
题目描述
给定一个由n（1<=n<=100）行数字组成的数字三角形。设计一个算法，计算出从三角形的底至顶的一条路径。使该路径经过的数字总和最小。路径的每一步。
只能向左下或者右下行走
输入格式
第一行一个数字n。

第2至n+1行，每行i个数字，i值为行号减1。

输出格式
一个数字，表示路径总和最小。
输入样例 复制
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
输出样例 复制
17

他说“从三角形的底至顶的一条路径”可是后面又说“只能向左下或者右下行走”这不矛盾吗？

应该是写错了

意思理解就行了

#include<bits/stdc++.h>
using namespace std;
int n,mx,sum,v[105][105],d[4][2]={{-1,0},{1,0},{0,-1},{0,1}},t,aa,bb,cc,dd,f;
char a[105][105];
void dfs(int si,int sj){
if(si==cc&&sj==dd){
cout<<"YES\n";
f=1;
}else{
for(int i=0;i<4;i++){
int nexti=si+d[i][0];
int nextj=sj+d[i][1];
if(nexti>=1&&nexti<=n&&nextj>=1&&nextj<=n&&a[nexti][nextj]=='.'&&v[nexti][nextj]==0){
v[nexti][nextj]=1;
dfs(nexti,nextj);
}
}
}
}
int main() {
cin>>t;
while(t--){
cin>>n;
f=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cin>>a[i][j];
}
}
cin>>aa>>bb>>cc>>dd;
aa++,bb++,cc++,dd++;
if(a[aa][bb]=='#'){
cout<<"NO\n";
}else{
v[aa][bb]=1;
dfs(aa,bb);
if(f==0){
cout<<"NO\n";
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
v[i][j]=0;
}
}
}
return 0;
}

5 limingzhe 李铭哲 91

#include <bits/stdc++.h>
using namespace std;
double dp[105];
double f[105];
double a[105];
int n;
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
dp[1]=100;
f[1]=a[1];
for(int i=2;i<=n;i++){
dp[i]=max(dp[i-1],f[i-1]/(a[i]/100));
f[i]=max(dp[i-1]*(a[i]/100),f[i-1]);
}
cout<<fixed<<setprecision(2)<<dp[n];
return 0;
}
是埃氏筛法