21th[동적 기획] 노면 수리
3073 단어 동적 기획
【제목 설명】:
FJ는 농장에 있는 울퉁불퉁한 흙길을 잘 보수할 계획이다.젖소들의 요구에 따라 수리한 노면의 높이는 상승하거나 하락해야 한다. 즉, 높이 상승과 높이 하락의 길은 수리한 노면에 동시에 나타날 수 없다는 것이다.길 전체가 N단으로 나뉘었고 N개의 정수 A1, ... , A_N은 각 구간의 높이를 순서대로 묘사했다.FJ는 N개의 원소가 꼭 포함된 상승하지 않거나 하락하지 않는 서열 B 를 찾고 싶어 한다1, ... , B_N, 수리한 길의 각 구간의 높이로 한다.매 구간의 도로 매트리스를 높이거나 낮은 단위로 파는 비용이 같기 때문에 도로 보수의 총 지출은 다음과 같이 나타낼 수 있다. |A1 - B_1| + |A_2 - B_2| + ... + |A_N - B_N|이 공사에서 FJ의 최소 지출이 얼마인지 계산해 보세요.FJ는 당신에게 이 지출이 2^31-1을 초과하지 않을 것을 보증합니다.
[설명 입력]:
행 1: 정수 1개 입력: N
두번째...N+1 행: i+1 동작 1 정수: Ai
【출력 설명】:
1개의 정수를 출력하면 FJ가 도로를 높이가 상승하지 않거나 높이가 하락하지 않는 최소 비용을 나타낸다
[샘플 입력]:
7
1
3
2
4
5
3
9[샘플 출력]:
3[시간 제한, 데이터 범위 및 설명]:
시간: 1s 공간: 128M
1 <= N <= 2,000
0 <= A_i <= 1,000,000,000
FJ는 첫 번째 높이가 3인 구간의 높이를 2로 줄이고 두 번째 높이가 3인 구간의 높이를 5로 늘리며 총 비용은|2-3|+|5-3|=3이며 각 구간의 높이는 1,2,2,4,5,9이다.
먼저 정렬하고 X로 기록하다
f[i][j]는 i개수 높이가 j개수보다 높은 수정 수량을 나타낸다.
f[i][j]=min(f[i][j-1],f[i-1][j]+abs(a[i]-x[j]));#include
#include
#include
using namespace std;
int a[2005],f[2005][2005],b[2005],x[2005];
int abs(int n){
return n>0?n:-n;
}
int main(){
int n,i,j,m=-1,s=1<<30;
scanf("%d",&n);
for(i=1;i<=n;i++){
scanf("%d",&a[i]);
b[n-i+1]=x[i]=a[i];
}
sort(x+1,x+n+1);
for(i=1;i<=n;i++){
for(j=1;j<=n;j++){
if(j==1){
f[i][j]=f[i-1][j]+abs(a[i]-x[j]);
}
else{
f[i][j]=min(f[i][j-1],f[i-1][j]+abs(a[i]-x[j]));
}
if(i==n){
s=min(s,f[i][j]);
}
}
}
for(i=1;i<=n;i++){
for(j=1;j<=n;j++){
if(j==1){
f[i][j]=f[i-1][j]+abs(b[i]-x[j]);
}
else{
f[i][j]=min(f[i][j-1],f[i-1][j]+abs(b[i]-x[j]));
}
if(i==n){
s=min(s,f[i][j]);
}
}
}
printf("%d
",s);
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
01 가방, 완전 가방, 다중 가방 dp(동적 기획 입문 dp)01 가방은 2진법으로 직접 표시할 수 있지만 데이터 양이 너무 많으면 시간을 초과하는 것이 폭력이다.01 가방의 사상은 바로 이 물품에 대해 내가 넣은 가치가 큰지 안 넣은 가치가 큰지 비교하여 방정식 f[i][v...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
