Java实现蓝桥杯算法提高宰羊

试题算法提高宰羊

资源限制

时间限制：1.0s 内存限制：256.0MB

问题描述

　　炫炫回了内蒙，肯定要吃羊肉啦，所有他家要宰羊吃。

　　炫炫家有N只羊，羊圈排成一排，标号1~N。炫炫每天吃掉一只羊（这食量！其实是放生啦），吃掉的羊的邻居会以为它被放生了，然后又会告诉他们的邻居，这样一直传播下去，除非某个邻居已经被“放生”了。每一天，所有知道某羊被“放生”了这个消息的羊都会很不满，如果不给他们巧克力的话，他们就会很造反，炫炫已经知道他要吃掉哪些羊，他可以任意安排吃的顺序，然后使巧克力的用量最小，请求出这个最小值。

输入格式

　　本题有多组数据，第一行为数据组数T。

　　对于每组数据

　　第一行：两个用空格隔开的整数：N和M，表示羊的数量和需要吃掉的数量

　　第二行：有M个数，表示要吃那些羊。

输出格式

　　T行，为每组数据的答案。

样例输入

2

8 1

3

20 3

3 6 14

样例输出

7

35

数据规模和约定

　　T=10

　　N<=10000

　　M<=100

待杀的羊:…a1…a2…a3…a4…an…待杀的羊:…a1…a2…a3…a4…an…

如果选择了ak这个羊先杀，区间将被分为两段[a1,ak],[ak,an],所以可以使用区间DP来分段处理

PS：

这么写可以少写一层循环，提高效率

就因为多输出了一行空格，导致问题死活出不来

***你个*****

 

import java.util.ArrayList;

import java.util.Arrays;

import java.util.Scanner;

public class 宰羊 {

    public static void main(String[] args) {

        int t,n,m;

        int [] num=new int [100+2];

        int [] [] dp=new int [100+2][100+2];

        ArrayList<Integer> list = new ArrayList<>();

        Scanner sc = new Scanner(System.in);

          t = sc.nextInt();

        while ( t-->0){

            n=sc.nextInt();

            m=sc.nextInt();

            for (int i =1;i<=m;i++){

                num[i]=sc.nextInt();

            }

            num[0] = 0;

            num[m + 1] = n + 1;

            for(int len=1;len<=m;len++)

                for(int l=1;l + len - 1<=m;l++)

                {

                    int r = len + l - 1;

                    if(len == 1)

                    {

                        dp[l][r] = num[r + 1] - num[l - 1] - 2;

                    }

                    else

                    {

                        dp[l][r] = 10000000;

                        for(int i=l;i<=r;i++)

                            dp[l][r] = Math.min(dp[l][r],num[r + 1] - num[l - 1] - 2 + dp[l][i - 1] + dp[i + 1][r]);

                    }

                }

           list.add(dp[1][m]);

        }

        sc.close();

        for (int i:list){

            System.out.println(i);

        }

    }

}

巴特西

Java实现蓝桥杯算法提高宰羊

试题算法提高宰羊

最新文章

热门文章

巴特西

Java实现 蓝桥杯 算法提高 宰羊

试题 算法提高 宰羊

最新文章

热门文章

Java实现蓝桥杯算法提高宰羊

试题算法提高宰羊