BZOJ 1564 NOI 2009 포크 찾기 트리 동적 계획
바뀐 후의 권한값은 같을 수 없지만 임의의 실수로 바꿀 수 있고 대가가 바뀐 크기와 무관하기 때문에 사실 같든 안 같든 상관없다
우선 키 값은 변경할 수 없습니다. 균형 트리의 중간 순서는 키 값이 점차 증가하기 때문에 중간 순서는 일정합니다. 우선 키 값에 따라 중간 순서를 정렬합니다.
w는 크지만 중복되지 않으므로 w이산화
그리고 DP가 문제야.우리는 f[i][j][w]로 하여금 i~j의 노드에서 하나의 나무를 구성하고 모든 노드의 권한이 w의 최소 대가보다 크다는 것을 나타낸다
그러면 상태가 이동할 때 새 하위 트리의 뿌리 노드 k를 매거하는 두 가지 업데이트 방식이 있습니다
1. k의 권한을 w로 직접 바꾸면 f[i][j][w]=min(f[i][j][w], f[i][k-1][w]+f[k+1][j][w]+K+i~j의 접근 빈도의 합계).
2. k의 권한이 w보다 크면 f[i][j][w]=min(f[i][j][w], f[i][k-1][a[k].weight]+f[k+1][j][a[k].weight]+i~j의 방문 빈도의 합계).
상태는 n^3, 매거k는 n, 모두 O(n^4), n<=70, 딱 끊겼어요.
DP의 순서와 초치에 주의하세요. 이 문제는 기억화 검색을 할 수 있어요. 그러면 순서와 초치에 신경 쓰지 않아도 돼요.
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define M 100
using namespace std;
int f[M][M][M];
int n,K,ans=0x3f3f3f3f;
struct abcd{
int value;
int weight;
int frequency;
}a[M];
bool operator < (const abcd &x,const abcd &y)
{
return x.value < y.value;
}
pair<int,int>b[M];
int main()
{
int i,j,k,w;
cin>>n>>K;
for(i=1;i<=n;i++)
scanf("%d",&a[i].value);
for(i=1;i<=n;i++)
scanf("%d",&a[i].weight);
for(i=1;i<=n;i++)
scanf("%d",&a[i].frequency);
sort(a+1,a+n+1);
for(i=1;i<=n;i++)
b[i].first=a[i].weight,b[i].second=i;
sort(b+1,b+n+1);
for(i=1;i<=n;i++)
a[b[i].second].weight=i;
for(i=1;i<=n;i++)
a[i].frequency+=a[i-1].frequency;
memset(f,0x3f,sizeof f);
for(i=1;i<=n+1;i++)
for(w=0;w<=n;w++)
f[i][i-1][w]=0;
for(w=n;~w;w--)
for(i=n;i;i--)
for(j=i;j<=n;j++)
for(k=i;k<=j;k++)
{
//if( &f[i][j][w]==&f[1][4][1] && k==3 )
// i++,i--;
if(a[k].weight>=w)
f[i][j][w]=min( f[i][j][w] , f[i][k-1][a[k].weight] + f[k+1][j][a[k].weight] + a[j].frequency - a[i-1].frequency );
f[i][j][w]=min( f[i][j][w] , f[i][k-1][w] + f[k+1][j][w] + K + a[j].frequency - a[i-1].frequency );
}
for(w=0;w<=n;w++)
ans=min(ans,f[1][n][w]);
cout<<ans<<endl;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 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에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
