http://acm.zzuli.edu.cn/problem.php?id=1654
浏览数：269 /
时间：2015年06月09日
1654: D:数塔塔塔塔塔塔
Time Limit: 1 Sec Memory Limit: 128 MB Submit: 154 Solved: 55SubmitStatusWeb Board
Description
.png)
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;
}
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
