如何花最少的錢購(gòu)買蔬菜

Description

Rahul wanted to purchase vegetables mainly brinjal, carrot and tomato. There are N different vegetable sellers in a line. Each vegetable seller sells all three vegetable items, but at different prices. Rahul, obsessed by his nature to spend optimally, decided not to purchase same vegetable from adjacent shops. Also, Rahul will purchase exactly one type of vegetable item (only 1 kg) from one shop. Rahul wishes to spend minimum money buying vegetables using this strategy. Help Rahul determine the minimum money he will spend.

拉胡爾想買的蔬菜主要是茄子、胡蘿卜和西紅柿。有N個(gè)不同的蔬菜小販在排隊(duì)。每個(gè)蔬菜賣家都出售這三種蔬菜，但價(jià)格不同。拉胡爾被自己的消費(fèi)天性所困擾，決定不從鄰近的商店購(gòu)買同樣的蔬菜。此外，拉胡爾只會(huì)從一家商店購(gòu)買一種蔬菜(只有1公斤)。拉胡爾希望用這種策略花最少的錢買蔬菜。幫助拉胡爾確定他將花費(fèi)的最低金額。

Input

First line indicates number of test cases T. Each test case in its first line contains N denoting the number of vegetable sellers in Vegetable Market. Then each of next N lines contains three space separated integers denoting cost of brinjal, carrot and tomato per kg with that particular vegetable seller.

第一行表示測(cè)試用例的數(shù)量t。第一行中的每個(gè)測(cè)試用例包含N，表示蔬菜市場(chǎng)中蔬菜銷售者的數(shù)量。接下來的N行每一行都包含三個(gè)用空格分隔的整數(shù)，分別表示菜販每公斤茄子、胡蘿卜和番茄的成本。

Output

For each test case, output the minimum cost of shopping taking the mentioned conditions into account in a separate line.
Constraints:1 <= T <= 101 <= N <= 100000 Cost of each vegetable(brinjal/carrot/tomato) per kg does not exceed 10^4

對(duì)于每個(gè)測(cè)試用例，在單獨(dú)的行中輸出考慮了上述條件的最低購(gòu)物成本。
約束條件:1 <= T <= 101 <= N <= 100000每公斤蔬菜(茄子/胡蘿卜/西紅柿)的成本不超過10^4

Sample Input

1
3
1 50 50
50 50 50
1 50 50

Sample Output

52

Solution

money[i][j]表示在第i+1個(gè)賣家處購(gòu)買第j+1種蔬菜時(shí)的最低價(jià)格

public class LeastMoneyToBuyVegetable {

    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int caseNum = in.nextInt();
        for(int i = 0; i < caseNum; i++){
            int sellerNum = in.nextInt();
            int vegetableNum = 3;
            int[][] vegetable = new int[sellerNum][vegetableNum];
            for(int j = 0; j < sellerNum; j++){
                for(int k = 0; k < vegetableNum; k++){
                    vegetable[j][k] = in.nextInt();
                }
            }
            System.out.println(getLeastMoney(sellerNum, vegetable));
        }
    }

    public static int getLeastMoney(int sellerNum, int[][] vegetable){
        int vegetableNum = 3;
        int[][] money = new int[sellerNum][vegetableNum];
        for(int i = 0; i < vegetableNum; i++){
            money[0][i] = vegetable[0][i];
        }
        for(int i = 1; i < sellerNum; i++){
            for(int j = 0; j < vegetableNum; j++){
                money[i][j] = Math.min(money[i - 1][(j + 1) % vegetableNum], money[i - 1][(j + 2) % vegetableNum]) + vegetable[i][j];
            }
        }
        int leastMoney = Integer.MAX_VALUE;
        for(int i = 0; i < vegetableNum; i++){
            if(money[sellerNum - 1][i] < leastMoney){
                leastMoney = money[sellerNum - 1][i];
            }
        }
        return leastMoney;
    }
}