[BZOJ2436] [Noi2011] Noi 카니발(dp)
제목 설명
전송문
문제풀이
매우 신기한 dp문제는 시험장에서 생각해 내는 것이 매우 어렵다고 느낀다.
먼저 첫 번째 질문에 대해 구간을 분리하면 모든 시간이 O(n)급으로 변한다.sum[i][j]는 시간 i~j 내에 몇 개의 활동이 있는지 미리 처리할 수 있습니다.f[i][j]를 설정하면 i시간까지 첫 번째 장소에서 j장 이벤트를 개최했을 때 두 번째 장소에서 최대 몇 개의 이벤트를 개최했는지를 나타낸다.f를 구하는 과정은 O(n3)의 dp를 사용하여 f[i][j]=max{f[i-3-1][j], f[k][j]+sum[k+1][i], f[k][j-sum[k+1][i]]}로 각각 행사를 하지 않겠다고 표시하고 2번 장소에서 행사를 하고 1번 장소에서 행사를 한다.그러면 첫 번째 질문의 답은 max{min(i,f[time][i])}입니다.
두 번째 질문에 같은 방법으로 g[i][j]가 거꾸로 순서가 i가 되었을 때 첫 번째 장소에서 j개 행사를 개최했을 때 두 번째 장소에서 최대 몇 개의 행사를 개최했는지 구한다.dp[i][j]를 설정하면 i~j 이 부분의 모든 활동이 동시에 어느 장소의 최대 답안을 선택한 것을 나타낸다.분명히 우리가 구간(l,r)을 선택해야 한다면 답은max{dp[i][j](i<=x,j>=y)}이다
dp[i][j]는 어떻게 구합니까?dp[i][j]=max{min(min(x+y,f[i−1][x]+g[j+1][y])+sum[i][j],max(x+y,f[i−1][x]+g[j+1][y]))} . 이렇게 복잡도는 O(n4)이다.
어떻게 최적화할 것인가를 고려하다.우리가 x가 상승함에 따라 y도 증가한다고 가정하면 f[i-3-1][x]와 g[j+1][y]는 모두 증가하지 않는다.x+y와 f[i-3-1][x]+g[j+1][y]를 최대한 평균적으로 고려하면 이런 상황은 나타날 수 없다.그래서 우리는 x가 상승함에 따라 가장 좋은 곳의 y값은 단조롭고 증가하지 않는다는 결론을 얻었다.시간의 복잡도는 O(n3)까지 최적화할 수 있다.
코드
#include
#include
#include
#include
using namespace std;
#define N 205
int n,s,t,xx,lsh,ans,inf;
int X[N*2],p[N*2],loc[N*2],sum[N*2][N*2],f[N*2][N],g[N*2][N],dp[N*2][N*2];
struct hp{int l,r;}show[N];
inline int cmp(int a,int b)
{
return X[a]inline int get(int i,int j,int x,int y)
{
if (f[i-1][x]==inf||g[j+1][y]==inf) return inf;
return min(min(x+y,f[i-1][x]+g[j+1][y])+sum[i][j],max(x+y,f[i-1][x]+g[j+1][y]));
}
int main()
{
scanf("%d",&n);
for (int i=1;i<=n;++i)
{
scanf("%d%d",&s,&t);
X[++xx]=s,X[++xx]=s+t-1;
}
for (int i=1;i<=xx;++i) p[i]=i;
sort(p+1,p+xx+1,cmp);X[0]=-1;
for (int i=1;i<=xx;++i)
if (X[p[i]]!=X[p[i-1]]) loc[p[i]]=++lsh;
else loc[p[i]]=lsh;
xx=0;
for (int i=1;i<=n;++i)
show[i].l=loc[++xx],show[i].r=loc[++xx];
for (int i=1;i<=lsh;++i)
for (int j=i;j<=lsh;++j)
for (int k=1;k<=n;++k)
if (show[k].l>=i&&show[k].r<=j)
sum[i][j]++;
memset(f,128,sizeof(f));
inf=f[0][0];
f[0][0]=0;
for (int i=1;i<=lsh;++i)
for (int j=0;j<=sum[1][i];++j)
{
f[i][j]=f[i-1][j];
for (int k=0;k1][i]);
if (j-sum[k+1][i]>=0) f[i][j]=max(f[i][j],f[k][j-sum[k+1][i]]);
}
}
ans=0;
for (int i=0;i<=n;++i)
ans=max(ans,min(i,f[lsh][i]));
printf("%d
",ans);
memset(g,128,sizeof(g));
g[lsh+1][0]=0;
for (int i=lsh;i>=1;--i)
for (int j=0;j<=n;++j)
{
g[i][j]=g[i+1][j];
for (int k=lsh+1;k>i;--k)
{
g[i][j]=max(g[i][j],g[k][j]+sum[i][k-1]);
if (j-sum[i][k-1]>=0) g[i][j]=max(g[i][j],g[k][j-sum[i][k-1]]);
}
}
for (int i=1;i<=lsh;++i)
for (int j=i;j<=lsh;++j)
{
int y=n;
for (int x=0;x<=n;++x)
{
int now=get(i,j,x,y);
while (y&&now<=(t=get(i,j,x,y-1))){now=t; y--;}
dp[i][j]=max(now,dp[i][j]);
}
}
for (int k=1;k<=n;++k)
{
ans=0;
for (int i=1;i<=show[k].l;++i)
for (int j=show[k].r;j<=lsh;++j)
ans=max(ans,dp[i][j]);
printf("%d
",ans);
}
}
총결산
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
49일차 - 2022.04.20Baekjoon에서 문제풀이 1) 문제 : 첫째 줄에는 별 1개, 둘째 줄에는 별 2개, N번째 줄에는 별 N개를 찍는 문제/ 첫째 줄에 N(1 ≤ N ≤ 100)이 주어진다. 첫째 줄부터 N번째 줄까지 차례대로 별...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.