우선 대기 열의 간단 한 이야기 (예제: 나무 막대 자 르 기)

제목 링크:http://39.108.226.55/problem/201802287
 
Description
 
이 토끼 의 작은 재 는 긴 나무 막대 기 를 N 단 으로 잘라 야 한다.각 단락 의 길 이 는 각각 L1, L2,..., LN (1 < = L1, L2,..., LN < = 1000 이 고 모두 정수) 개의 길이 단위 이다.우 리 는 절단 할 때 정수 점 에서 만 자 르 고 목재 손실 이 없다 고 생각한다.
그러나 토끼 의 작은 재 는 절단 에 들 어 가 는 체력 이 이 나무 막대 의 길이 와 정비례 하 는 것 을 발견 했다. 절단 길이 가 1 인 나무 막대 기 를 설치 하 는 데 1 단위 의 체력 을 써 도 무방 하 다.예 를 들 어 N = 3, L1 = 3, L2 = 4, L3 = 5 의 경우 나무 막대 기 는 원래 길이 가 12 이 고 목 수 는 여러 가지 절단 방법 이 있 습 니 다. 예 를 들 어 12 를 3 + 9 로 자 르 고 12 의 체력 을 소비 한 다음 에 9 를 4 + 5 로 자 르 면 9 의 체력 을 소비 하고 모두 21 의 체력 을 소비 할 수 있 습 니 다.또한 12 를 4 + 8 로 썰 어 12 체력 을 소모 하고 8 을 3 + 5 로 썰 어 8 체력 을 소모 해 총 20 체력 을 소모 할 수 있다.후 자 는 전자 보다 체력 을 더 아 끼 는 것 이 분명 하 다.그렇다면 토끼 먼지 는 적어도 얼마나 많은 체력 을 들 여야 절단 임 무 를 완성 할 수 있 을 까?
 
Input
 
1 줄: 1 개의 정수 N (2 < = N < = 500) 2 - N + 1 줄: 줄 당 1 개의 정수 Li (1 < = Li < = 1000).
 
Output
 
출력 최소 체력 소모.
 
Sample Input 1 

3
3
4
5

Sample Output 1

19

사내 가 문 제 를 쓰 는 방향 을 보고 우선 대열 로 배 웠 다.배 울 때 갑자기 우선 대기 열 을 쓰 지 않 아 도 된다 는 생각 이 들 었 어 요. 우선 대기 열 을 모 의 해서.......................................
제목 이 명확 합 니 다. 우 리 는 그 에 게 각 도 를 바 꾸 어 해결 해 주 었 습 니 다. 확실 하지 않 으 면 받 습 니 다. 이 흩 어 진 나무 막대 기 를 큰 나무 막대 로 만 들 고 가장 적은 힘 을 썼 습 니 다. 자, 그러면 우 리 는 매번 가장 작은 나무 막대 기 를 두 개 만 사용 하면 됩 니 다. 그 에 게 큰 나무 막대 기 를 만들어 다시 찾 아 보면 해결 할 수 있 습 니 다. 이것 은 n * log (n) 의 방법 입 니 다. 괜 찮 을 것 같 습 니 다.
ac：

#include
#include
#include

//#include

그 다음 에 우선 대기 열 입 니 다. 위의 느낌 은 이 문제 가 너무 간단 하고 다른 변수 가 없 지만 우선 대기 열 을 배 워 야 합 니 다.
우선 순위 의 자세 한 설명 은 링크 가 있 습 니 다:http://blog.csdn.net/c20182030/article/details/70757660。
우선 대기 열의 사용 형식 에 주의 하 십시오:

struct node{
    int first,secend;
};

struct cmp{
    bool operator()(const node &a,const node &b){
        return a.first>b.first;//     first      
    }
};


priority_queue,cmp> que;


//-----           
/*
priority_queue que;
    ：
input：
1 2 3 4 5 6 7 8 9 
output：
9 8 7 6 5 4 3 2 1 
*/

물론 wo 'm 는 구조 체 내부 의 정렬 규칙 을 직접 정의 한 다음 에 일반적인 우선 대기 열 을 직접 사용 할 수 있 습 니 다. 예:

//x        
struct node{
	int x,l;
    //     
	bool operator < (const node & a)const{
		return xa.x;
	}
};

이렇게 하면 priorityqueue que;
정렬
 
 

less //    
greater //    

#include
#include
#include

//#include