POJ 1163ディジタル三角形問題(DP)
4487 ワード
http://poj.org/problem?id=1163
単純ダイナミックプランニング
View Code
単純ダイナミックプランニング
1 #include<stdio.h>
2 #define M 1000
3 int d[M][M];
4 int a[M][M];
5 int n;
6 int main()
7 {
8 int i,j;
9 scanf("%d",&n);
10 for(i=1;i<=n;i++)
11 {
12 for(j=1;j<=i;j++)
13 scanf("%d",&d[i][j]);
14 }
15 for(j=1;j<n;j++)
16 a[n][j]=d[n][j];
17 for(i=n;i>1;i--)
18 for(j=1;j<=i;j++)
19 {
20 if(a[i][j]>a[i][j+1])
21 a[i-1][j]=a[i][j]+d[i-1][j];
22 else
23 a[i-1][j]=a[i][j+1]+d[i-1][j];
24 }
25 printf("%d
",a[1][1]);
26 return 0;
27 }
View Code