NOIp2018 보급팀 - 나룻배
1214 단어 dp
제목 링크:https://www.luogu.org/problemnew/solution/P5017
1. 느낌은 일종의 선형적인 시간을 차원으로 하는 dp이다. 다시 한 번 범위: 4*10^6는 큰 문제가 없다.
2. f[t]의 의미에 대해 생각하기 시작한다. 나룻배가 t분에 떠날 때 모든 사람이 가장 적은 대기 시간을 갖는다.
3. 이어서 이동: 우선 t보다 일찍 출발 2*m 분 전(낭비야)의, m분 후의(이동 불가) 모두 고려하지 않아도 된다
4. 마지막으로 j가 i-2*m에서 i-m로 이동하는 방안을 매거하고 이 시간 동안의 이동을 더하면 우리의 답이다.
(5. 하지만 CCF의 기계는 한마디로 말하기 어려우니 최적화를 고려해보자...i-m 사이에 아무도 없다면 i는 사실 직접 값을 부여할 수 있으니 계산하지 않아도 된다)
over
#include
using namespace std;
const int maxn=5000005;
int t[maxn],num[maxn],st[maxn],f[maxn];int T=0;
int main()
{
int n,m;scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d",&t[i]);num[t[i]]++;
T=max(T,t[i]);
st[t[i]]+=t[i];
}
for(int i=1;i<=T+m-1;i++)
{
num[i]+=num[i-1];st[i]+=st[i-1];
}
int minv=0x3f3f3f3f;
for(int i=1;i<=T+m-1;i++)
{
if(i>=m&&num[i-m]==num[i]) {f[i]=f[i-m];continue;}// ，
f[i]=num[i]*i-st[i];
for(int j=i-m;j>=max(0,i-2*m);j--)
{
f[i]=min(f[i],f[j]+(num[i]-num[j])*i-(st[i]-st[j]));
}
}
for(int i=T;i<=T+m-1;i++) minv=min(minv,f[i]);
printf("%d",minv);
return 0;
} 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【경쟁 프로 전형적인 90문】008의 해설(python)의 해설 기사입니다. 해설의 이미지를 봐도 모르는 (이해력이 부족한) 것이 많이 있었으므로, 나중에 다시 풀었을 때에 확인할 수 있도록 정리했습니다. ※순차적으로, 모든 문제의 해설 기사를 들어갈 예정입니다. 문자열...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
