NKOJ 2151 [단조 로 운 대열] 봉화 전달 단조 로 운 대열 최적화 DP
2231 단어 ACM_동적 계획ACM_데이터 구조
단조 로 운 대기 열 을 이용 하여 dp 최적화
【 단조 로 운 대열 】 봉화 전달
Time Limit:10000MS Memory Limit:65536K Total Submit:91 Accepted:36 Case Time Limit:1000MS
Description
봉화 대 는 봉 수 라 고도 불 리 며 중요 한 방어 시설 이다. 보통 험 한 곳 이나 교통 요로 에 세 워 진다. 적정 이 발생 하면 낮 에는 나 무 를 태 우 고 짙 은 연 기 를 통 해 밤 에는 마른 나 무 를 태 우 고 불빛 으로 군정 을 전달한다. 어느 두 도시 사이 에는 n 개의 봉화대 가 있 는데 봉화대 마다 신 호 를 보 내 는 데 는 일정한 대가 가 있다. 정 보 를 정확하게 전달 하기 위해 m 개 봉화 대 에 있다.화장대 에는 적어도 한 개의 신호 가 있어 야 합 니 다. 현재 n, m 와 모든 봉화대 에서 보 내 는 신호 의 대가 (정수) 를 입력 하 십시오. 총 최소 얼마의 대 가 를 써 야 적군 이 습격 할 때 정 보 는 이 두 도시 사이 에서 정확하게 전 달 될 수 있 는 지 계산 하 십시오!!
Input
첫 번 째 줄 에는 n, m (1 = n, m < = 1000000) 가 각각 n 개의 봉화대 가 있 고 m 개의 봉화대 에서 적어도 하 나 는 신 호 를 보 내야 한다. 두 번 째 행 위 는 n 개 로 모든 봉화대 의 대 가 를 나타 낸다.
Output
하나의 숫자, 즉 최소 의 대가.
Sample Input
5 3
1 2 5 6 2
Sample Output
4Hint
보증 답안 < 109.
Source
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define all(x) (x).begin(), (x).end()
#define for0(a, n) for (int (a) = 0; (a) < (n); (a)++)
#define for1(a, n) for (int (a) = 1; (a) <= (n); (a)++)
typedef long long ll;
typedef pair pii;
const int INF =0x3f3f3f3f;
const int maxn=1000000 ;
int n,m,dp[maxn+10],q[maxn+10],a[maxn+10];
void work()
{
int rear=1,front=1,ans=INT_MAX;
dp[0]=0;
q[rear++]=0;
for(int i=1;i<=n;i++)
{
while(front=dp[i] )
{
rear--;
}
q[rear++]=i;
if(i>= n-m+1)
{
ans=min(ans,dp[i]);
}
}
printf("%d
",ans);
}
int main()
{
scanf("%d%d",&n,&m);
{
for1(i,n) scanf("%d",&a[i]);
work();
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
문제 풀이 보고서 의 CodeForces 91B QueueOtherwise, print the i-th walrus's displeasure: the number of other walruses that stand between him and the furthest fro...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
