whyisyoung's Blog

If you can not persist, you will never succeed :)

EOJ 1824 Solution Report - 数塔III

| Comments

原题: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;
}

Comments