BZOJ 2436: [Noi 2011] Noi 카니발
4311 단어 DP
l[i][j]=max(l[k][j]+c[k][i],l[k][j−c[k][i]])(k∈[0,i−1])
r [i] [j] (구간 [i, Tmax]) 구법 동 리 를 거꾸로 하면 돼.
왜 거꾸로 하 냐 면 두 번 째 질문 을 해 야 되 니까.
우리
강제 선택 i j 구간 의 모든 것 이 작은 사람 이 얼마나 많은 지
g[i][j]=max(l[i][x]+c[i][j]+r[j][y])(x,y∈[0,n])
그리고 사실은 x 가 고정 되 었 을 때 위의 값 은 y 단조 에 관 한 것 이다.그리고 n ^ 3 으로 끝 낼 수 있어 요.
g 배열 이 좌우 로 최대 로 확장 할 수 있다 는 것 을 잊 지 마 세 요.
독자 가 왜 이 안에 단조 성에 대한 증명 이 있 는 지 알 고 싶다 면 잘 그 렸 습 니 다.
http://www.cnblogs.com/Konjakmoyu/p/6602274.html
그렇게 오래 했 는데 56 이면 돼.
#include
#define me(a,x) memset(a,x,sizeof a)
using namespace std;
const int N=201,M=402;
inline int read()
{
char ch=getchar(); int x=0,f=1;
while(ch'9'){if(ch=='-')f=-1; ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();}
return x*f;
}
int s[N],t[N],p[M],g[M][M],c[M][M],l[M][N],r[M][N];
int main()
{
int n=read(),i,j,x,y,m=0;
for(i=1;i<=n;i++)
p[++m]=s[i]=read(),p[++m]=t[i]=s[i]+read();
sort(p+1,p+1+m);
m=unique(p+1,p+1+m)-p-1;
for(i=1;i<=n;i++)
s[i]=lower_bound(p+1,p+1+m,s[i])-p,
t[i]=lower_bound(p+1,p+1+m,t[i])-p;
for(i=0;i<=m;i++)
{
for(j=1;j<=n;j++)if(s[j]>=i)c[i][t[j]]++;
for(j=i+1;j<=m;j++)c[i][j]+=c[i][j-1];
}
me(l,-10); me(r,-10); me(g,-10);
l[1][c[1][1]]=0,l[1][0]=c[1][1];
for(i=2;i<=m;i++)for(j=0;j<=n;j++)
for(x=1;x
l[i][j]=max(l[i][j],max(l[x][j]+c[x][i],l[x][j-c[x][i]]));
r[m][c[m][m]]=0,r[m][0]=c[m][m];
for(i=m-1;i>0;i--)for(j=0;j<=n;j++)
for(x=m;x>i;x--)
r[i][j]=max(r[i][j],max(r[x][j]+c[i][x],r[x][j-c[i][x]]));
int ans=0;
for(i=1;i<=m;i++)for(j=i;j<=m;j++)
{
for(y=c[j][m],x=0;x<=c[1][i];x++,y++)
for(;~y;y--)
{
int u=min(x+y,l[i][x]+c[i][j]+r[j][y]);
if(g[i][j]<=u)g[i][j]=u;
else break;
}
ans=max(ans,g[i][j]);
}
for(i=1;i<=m;i++)
for(j=m;j>=i;j--)g[i][j]=max(g[i][j],g[i][j+1]);
for(i=1;i<=m;i++)
for(j=i;j<=m;j++)g[i][j]=max(g[i][j],g[i-1][j]);
printf("%d
",ans);
for(i=1;i<=n;i++) printf("%d
",g[s[i]][t[i]]);
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[BOJ]11048(python)python 풀이 DP를 이용해 풀이 보통 이런 문제는 dfs나 bfs로 풀이하는 것이여서 고민을 했는데 이 문구 덕분에 DP 를 이용해 풀이할 수 있었다 뒤로 돌아가는 등의 경우를 고려하지 않아도 되기 때문이다 코...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.