BZOJ1864 [Zjoi2006] 트리플 트리 DP
2291 단어 BZOJ
f(i, j)로 i번째 노드가 j색을 칠할 때 하위 트리의 정점은 녹색이 가장 많은 개수를 나타내고 fs(i, j)는 가장 적은 개수를 나타낸다.상태 이동 방정식을 쓰기 쉽고 기억화 검색으로 실현됩니다.
그런 다음 입력의 경우 DFS 또는 스택을 사용하여 트리로 전환할 수 있습니다.
이 코드는 계속 간소화할 수 있을 것 같아서 이렇게 길어질 필요는 없다.
//BZOJ1864
#include
#include
#include
#include
#include
#include
#include
#include
//Red 0 Green 1 Blue 2
using namespace std;
const int MAXN=500010;
const int INF=1e9;
struct Node
{
int ch[2],s,f[3],fs[3];
Node() {f[0]=f[1]=f[2]=-1;fs[0]=fs[1]=fs[2]=-1;}
}a[MAXN];
stack S[2];
char str[MAXN];
int len,ans;
int getf(int x,int c)
{
if(a[x].f[c]!=-1) return a[x].f[c];
if(a[x].s==0)
{
if(c==1) a[x].f[c]=1;
else a[x].f[c]=0;
return a[x].f[c];
}
if(a[x].s==1)
{
for(int i=0;i<=2;i++)
if(i!=c) a[x].f[c]=max(a[x].f[c],getf(a[x].ch[0],i));
if(c==1) a[x].f[c]++;
return a[x].f[c];
}
if(a[x].s==2)
{
int l,r;
for(int i=0;i<=2;i++) if(i!=c) {l=i;break;}
for(int i=0;i<=2;i++) if(i!=c&&i!=l) {r=i;break;}
a[x].f[c]=max(a[x].f[c],getf(a[x].ch[0],l)+getf(a[x].ch[1],r));
a[x].f[c]=max(a[x].f[c],getf(a[x].ch[0],r)+getf(a[x].ch[1],l));
if(c==1) a[x].f[c]++;
return a[x].f[c];
}
}
int getfs(int x,int c)
{
if(a[x].fs[c]!=-1) return a[x].fs[c];
if(a[x].s==0)
{
if(c==1) a[x].fs[c]=1;
else a[x].fs[c]=0;
return a[x].fs[c];
}
if(a[x].s==1)
{
a[x].fs[c]=INF;
for(int i=0;i<=2;i++)
if(i!=c) a[x].fs[c]=min(a[x].fs[c],getfs(a[x].ch[0],i));
if(c==1) a[x].fs[c]++;
return a[x].fs[c];
}
if(a[x].s==2)
{
int l,r;
for(int i=0;i<=2;i++) if(i!=c) {l=i;break;}
for(int i=0;i<=2;i++) if(i!=c&&i!=l) {r=i;break;}
a[x].fs[c]=INF;
a[x].fs[c]=min(a[x].fs[c],getfs(a[x].ch[0],l)+getfs(a[x].ch[1],r));
a[x].fs[c]=min(a[x].fs[c],getfs(a[x].ch[0],r)+getfs(a[x].ch[1],l));
if(c==1) a[x].fs[c]++;
return a[x].fs[c];
}
}
int main()
{
scanf("%s",str+1);
len=strlen(str+1);
for(int i=0;i 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
BZOJ3930: [CQOI2015] 선택거의 짠 물고기일 거야.. 처음에 제목 yy에 대해 정확할 것 같고 복잡도 계산이 안 되는 검색을 했는데 잘 안 되는 것 같아서 DP를 생각하고 정확해 보이는 DP를 생각해서 끊었어요.그럼 용납하고 싶다......설...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
