DP-BZOJ-1617-[Usaco 2008 Mar]River Crossing 도하 문제
Farmer John과 그의 N (1 < = N < = 2500) 머리 젖소는 강을 건너려고 했지만, 그들의 모든 강을 건너는 도구는 단지 뗏목일 뿐이었다.젖소가 배를 저을 줄 모르기 때문에 전체 강을 건너는 과정에서 FJ는 반드시 시종일관 뗏목에 있어야 한다.이 기초 위에서 뗏목 위의 젖소 수가 1씩 증가할 때마다 FJ가 뗏목을 맞은편 기슭까지 젓는 데 더 많은 시간이 걸린다.FJ가 혼자 뗏목에 앉아 있을 때, 그가 뗏목을 맞은편 기슭까지 젓는 데 M (1 < = M < = 1000) 분이 걸린다.뗏목에 탑재된 젖소의 수가 i-1에서 i로 증가하면 FJ는 더 많이 써야 한다Mi(1<=M i <=1000)분에야 뗏목을 강을 건널 수 있다(즉, 배에 젖소 1마리가 있을 때 FJ는 M+M 1분을 들여 강을 건너야 하고, 배에 젖소 2마리가 있을 때 시간은 M+M 1+M 2분이 된다. 뒤에 있는 것은 이와 같이 유추한다).그렇다면 FJ는 최소한 얼마나 걸려야 모든 젖소를 맞은편 기슭까지 데려갈 수 있을까?물론 이 시간에는 FJ 혼자서 뗏목을 맞은편 기슭에서 저어 다음 젖소를 데려오는 시간이 포함돼야 한다.Input
3
4
6
100
1
설명 입력:
FJ는 젖소 다섯 마리를 데리고 외출했다.단독으로 뗏목을 저어 강을 건널 경우, FJ는 10분이 걸려서 가지고 간다
1마리면 13분, 2마리면 17분, 3마리면 23분, 4마리면 123분
5마리를 한꺼번에 싣는 데 걸리는 시간은 124분이다.
Sample Output 50
HINT
출력 설명:
Farmer John은 처음으로 젖소 세 마리를 데리고 강을 건널 때(23분) 혼자서 노를 저어 돌아왔다
(10분), 마지막으로 남은 젖소 2마리를 데리고 강을 건너는 데 걸린 시간은
23+10+17 = 50분.
문제풀이: 누드DP물문제입니다. 먼저 w[i]에게 한 번에 i마리를 데려가는 데 걸리는 시간을 표시하고, dp[i]는 i마리를 데려가는 데 걸리는 시간을 표시합니다.그럼 dp[i]=min(dp[i-j]+m+w[j]).마지막으로 dp[n]를 m에서 빼면 한 번 더 계산할 수 있기 때문이다.
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
const int INF=0x7fffffff;
using namespace std;
int n,m;
long long int w[2550],dp[2550];
int main()
{
cin >> n >> m;
w[0]=m;
for(int i=1;i<=n;i++)
{
scanf("%lld",&w[i]);
w[i]+=w[i-1];
}
for(int i=1;i<=n;i++)
{
dp[i]=INF;
for(int j=0;j<i;j++)
dp[i]=min(dp[i],dp[j]+w[i-j]+m);
}
cout << dp[n]-m << endl;
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
