codeforces 509F Progress Monitoring(구간 dp)
깊이 있는 검색 코드를 보여 줍니다. 이렇게 트리를 훑어본 결과는 직렬 b, 서로 다른 구조의 트리의 개수입니다.
문제 풀이:
구간 dp, 점차적인 방정식을 생각하기 시작했지만 점차적인 조건은 a[k+1]>a[i+1]를 생각하지 못했다.
상태 dp[i][j]는 i를 뿌리에서 j 위치로 하는 이 구간으로 구성된 하위 트리의 방안수입니다.
방정식 dp[i][j]+=dp[i+1][k]*dp[k][j]두 번째는 k에서 시작할 때 나무 전체를 연결하려면 반드시 같은 노드가 있어야 한다.조건 a[k+1]>a[i+1]이라는 조건도 사실 뚜렷하다. 후반부의 k+1은 합병된 나무의 뿌리 번호보다 작아야 한다. 이 서열을 돌려주는 것보다 작지 않으면 합법적이지 않다. 깊이 있는 검색에 따라 추측해 보면 알 수 있다.
#include<iostream>
#include<math.h>
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<vector>
#include<map>
using namespace std;
typedef long long lld;
const int oo=0x3f3f3f3f;
const lld OO=1e18;
const int Mod=1000000007;
const int maxn=500+5;
int a[maxn];
lld dp[maxn][maxn];
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
memset(dp,0,sizeof dp);
for(int i=1;i<=n;i++)
dp[i][i]=1;
for(int L=2;L<=n;L++)
{
for(int i=1;i+L-1<=n;i++)
{
int j=i+L-1;
for(int k=i+1;k<=j;k++)
if(k==j||a[k+1]>a[i+1])
dp[i][j]=(dp[i][j]+dp[i+1][k]*dp[k][j]+Mod)%Mod;
}
}
cout<<dp[1][n]<<endl;
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
