Java实现 蓝桥杯 算法提高 宰羊
125 浏览量
2020-12-22
23:22:30
上传
评论
收藏 108KB PDF 举报
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 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)
{
资源评论
