填寫問券˙抽7-11禮券工程師靠存股年領百萬股息輕忽小中風,當心變殘障不捨學生找「槌」 高中...
2012-04-20 18:46:31 人氣(228) | 回應(0) | 推薦(0) | 收藏(0) 上一篇 | 下一篇

[UVA][DP] 11002 - Towards Zero

0
收藏
0
推薦


 Problem C: Towards Zero 

The Problem

Have you ever heard of this game? The player jumps in a special game board under certain rules, so that the numbers he jumps on, after being linked up by plus or minus signs, get closest to zero.

The game board looks like the one shown in Figure 1.1. Its size is determined by the number of squares in the middle row N. (Figure 1.1 is an example where N = 4.)The player starts at the bottom-most square, then jumps in any of the directions shown in Figure 1.2. The game ends when the player reaches the topmost square. During the game, the player cannot jump out of the game board.Finally we write down the 2N-1 numbers in order, then insert plus or minus signs between each pair of adjoining numbers such that the result is closest to zero.

Let us look at the game board in Figure 1.1 as a example. We should get: 7+8+(-5)+(-2)-5-1-2=0, 7+10+(-7)-6+(-3)-3+2=0, 7+10+(-5)-10-5+1+2=0, or 7+10+(-5)+(-2)-5-3-2=0.

The Input

The first line of input contains N (1 ≤ N ≤ 30). The following 2N-1 lines give the numbers in the squares in the game board. The j-th number in the (i+1)-th line corresponds to the j-th number in the i-th row of the game board. (The numbers are all ≥ -50 and ≤ 50.)

Input contains multiple test cases, and it ends with a case where N = 0.

The Output

For each case, your output should print the absolute value of the result you get for each game board.

Sample Input

423 1-3 5 76 10 -2 20-7 -5 -810 87 0

Sample Output

0

由下而上把所有不重複的數字慢慢拓展, 採用 C++ 的 map

//C++ 2.000
#include <stdio.h>
#include <stdlib.h>
#include <map>
using namespace std;

int main() {
    map<int, int> record[60][30];
    int n, i, j, A[60][30];
    while(scanf("%d", &n) == 1 && n) {
        for(i = 0; i < 2*n-1; i++) {
            for(j = 0; j < n-abs(n-i-1); j++) {
                scanf("%d", &A[i][j]);
                if(i != 2*n-2)
                    A[i][j] = abs(A[i][j]);
                record[i][j].clear();
            }
        }
        record[2*n-2][0][A[2*n-2][0]] = 1;
        for(i = 2*n-2; i >= n; i--) {
            for(j = 0; j < n-abs(n-i-1); j++) {
                for(map<int, int>::iterator k = record[i][j].begin(); k != record[i][j].end(); k++) {
                    int v = k->first;
                    record[i-1][j][abs(v+A[i-1][j])] = 1;
                    record[i-1][j][abs(v-A[i-1][j])] = 1;
                    record[i-1][j+1][abs(v+A[i-1][j+1])] = 1;
                    record[i-1][j+1][abs(v-A[i-1][j+1])] = 1;
                }
            }
        }
        for(i = n-1; i >= 1; i--) {
            for(j = 0; j < n-abs(n-i-1); j++) {
                for(map<int, int>::iterator k = record[i][j].begin(); k != record[i][j].end(); k++) {
                    int v = k->first;
                    record[i-1][j][abs(v+A[i-1][j])] = 1;
                    record[i-1][j][abs(v-A[i-1][j])] = 1;
                    if(j) {
                        record[i-1][j-1][abs(v+A[i-1][j-1])] = 1;
                        record[i-1][j-1][abs(v-A[i-1][j-1])] = 1;
                    }
                }
            }
        }
        int min = 0xfffffff;
        for(map<int, int>::iterator i = record[0][0].begin(); i != record[0][0].end(); i++)
            if(abs(i->first) < min)
                min = abs(i->first);
        printf("%d\n", min);
    }
    return 0;
}

11002Towards ZeroDP
台長:Morris
人氣(228) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: UVA |
此分類下一篇:[UVA][V2] 11002 - Towards Zero
此分類上一篇:[UVA][DFS] 989 - Su Doku

我要回應
是 (若未登入"個人新聞台帳號"則看不到回覆唷!)
* 請輸入識別碼:
請輸入以下數字 (ex:123)

(有*為必填)
詳全文