原题：EOJ 1824
1. 题目描述：
一个正整数组成的三角形，第一行只有一个数, 除了最底行之外每个数的左下方和右下方各有一个数。如下图
1
3 2
4 10 1
4 3 2 20
从第一行的数开始, 每次都只能左下或右下走一格, 直到走到最下行, 将沿途经过的数加起来，求和的个位数最大是多少。
Note:
1≤N≤500,N 表示数塔高度
每行的数范围是 [0,99]
2. 解题思路
本题不满足最优子结构（两个数的个位数字之和可能为两位数），因为和的个位数字只可能是 0 - 9 其中的一个，改用如下状态定义：
d[i][j][k]
表示以 (i, j) 为根的子三角形的所有数之和的个位数若有为 k 的路径则取值为1， 否则取值为0（其中 k 为 0-9 ）
则解为满足 d[1][1][k] = 1 的最大 k 值。
初始数组 d 全部为 0， 从最底下一层开始算起，根据个位数字模 10 的情况，设置数组某些位为 1。 然后从下往上往左往右加，只需注意个位数字相加后模 10 即可，设置对应位为 1。
代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
|
//
// main.cpp
// eoj1824
//
// Created by whyisyoung on 3/26/14.
// Copyright (c) 2014 whyisyoung. All rights reserved.
//
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 102;
int a[maxn][maxn]; // the original tower
// d[i][j][k] 表示以 (i, j) 为根的子三角形的所有数之和的个位数若有为 k 的路径则取值为1， 否则取值为0（其中 k 为 0-9 ）
int d[maxn][maxn][10];
int solve(int n)
{
memset(d, 0, sizeof(d));
for(int i = 1; i <= n; ++i) {
d[n][i][a[n][i] % 10] = 1;
}
for(int i = n; i >= 1; --i) {
for(int j = 1; j <= i; ++j) {
for( int k = 0; k <= 9; ++k) {
if(d[i][j][k]) {
d[i - 1][j - 1][(k + a[i - 1][j - 1] % 10)] = 1;
d[i - 1][j][(k + a[i - 1][j]) % 10] = 1;
}
}
}
}
int ans = 0;
for(int k = 1; k <= 9; ++k) {
if(d[1][1][k]) {
if(k > ans)
ans = k;
}
}
return ans;
}
int main()
{
int C, N;
scanf("%d", &C);
while(C--) {
scanf("%d", &N);
memset(a, 0, sizeof(a));
for(int i = 1; i <= N; ++i) {
for(int j = 1; j <= i; ++j) {
scanf("%d", &a[i][j]);
}
}
cout << solve(N) << endl;
}
return 0;
}
|
