.png)
http://acm.zzuli.edu.cn/problem.php?id=1654
1654: D:数塔塔塔塔塔塔
Time Limit: 1 Sec Memory Limit: 128 MB Submit: 154 Solved: 55SubmitStatusWeb Board
Description
Input
.png)
Output
.png)
Sample Input
1 5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5
Sample Output
30 (0,0)-->(1,0)-->(2,0)-->(3,1)-->(4,1)
#include<stdio.h>
int main(void){
int a[100][100];
int d[100][100];
int h[100][100];
int n,m,i,j,t;
scanf("%d",&t);
while(t--){
scanf("%d",&n);
for(i=0;i<n;i++)
for(j=0;j<=i;j++)
scanf("%d",&a[i][j]);
for(j=0;j<n;j++)
d[n-1][j]=a[n-1][j];
for(i=n-2;i>=0;i--)
{
for(j=0;j<=i;j++){
if(d[i+1][j]>=d[i+1][j+1]){
d[i][j]=a[i][j]+d[i+1][j];
h[i][j]=0;}
else
{d[i][j]=a[i][j]+d[i+1][j+1];
h[i][j]=1;}
}}
printf("%d\n",d[0][0]);
printf("(0,0)");
j=0;
if(h[0][0]==1)
j=j+1;
for(i=1;i<n;i++){
printf("-->(%d,%d)",i,j);
if(h[i][j]==1)
j=j+1;}
printf("\n");
}
return 0;
}
int main(void){
int a[100][100];
int d[100][100];
int h[100][100];
int n,m,i,j,t;
scanf("%d",&t);
while(t--){
scanf("%d",&n);
for(i=0;i<n;i++)
for(j=0;j<=i;j++)
scanf("%d",&a[i][j]);
for(j=0;j<n;j++)
d[n-1][j]=a[n-1][j];
for(i=n-2;i>=0;i--)
{
for(j=0;j<=i;j++){
if(d[i+1][j]>=d[i+1][j+1]){
d[i][j]=a[i][j]+d[i+1][j];
h[i][j]=0;}
else
{d[i][j]=a[i][j]+d[i+1][j+1];
h[i][j]=1;}
}}
printf("%d\n",d[0][0]);
printf("(0,0)");
j=0;
if(h[0][0]==1)
j=j+1;
for(i=1;i<n;i++){
printf("-->(%d,%d)",i,j);
if(h[i][j]==1)
j=j+1;}
printf("\n");
}
return 0;
}
文章来自：http://www.cnblogs.com/chenlong123/p/4355137.html