如何花最少的钱购买蔬菜

如何花最少的钱购买蔬菜

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个不同的蔬菜小贩在排队。每个蔬菜卖家都出售这三种蔬菜，但价格不同。拉胡尔被自己的消费天性所困扰，决定不从邻近的商店购买同样的蔬菜。此外，拉胡尔只会从一家商店购买一种蔬菜(只有1公斤)。拉胡尔希望用这种策略花最少的钱买蔬菜。帮助拉胡尔确定他将花费的最低金额。

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.

第一行表示测试用例的数量t。第一行中的每个测试用例包含N，表示蔬菜市场中蔬菜销售者的数量。接下来的N行每一行都包含三个用空格分隔的整数，分别表示菜贩每公斤茄子、胡萝卜和番茄的成本。

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

对于每个测试用例，在单独的行中输出考虑了上述条件的最低购物成本。
约束条件: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个卖家处购买第j+1种蔬菜时的最低价格

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;
    }
}