【DP】AGC012F Prefix Median

1447 단어 DP

분석:


A수조를 정렬하고 B수조를 구성하는 것을 고려하다.
한 가지 성질 발견: 임의의 i, j가 존재하지 않고 j>i를 만족시킨다. B j < B i < B j + 1 또는 B j > B i> B j + 1은 임의의 i, j, 만족 j>i, B 가 존재하지 않는다.jB_i>B_{j+1} 임의의 i, j가 존재하지 않습니다. j>i를 만족시키고, BjBi>Bj+1은 명백하지만 매우 효과적입니다.한 번에 두 개만 넣기 때문에 중위수는 최대 한 걸음까지 움직인다.
이 성질이 있으면 뒤에서 앞으로 미룰 수 있고 매번 넣는 값은 이전의 값역에 있을 수 없다.그래서 현재 사용할 수 있는 값역보다 작거나 같은 값의 개수, 값역보다 큰 값의 개수를 기록할 수 있다.
#include
#include
#include
#include
#include
#define SF scanf
#define PF printf
#define MAXN 110
#define MOD 1000000007
#define eisiorti sort
using namespace std;
int a[MAXN];
int n;
int dp[MAXN/2][MAXN][MAXN];
int main(){
	SF("%d",&n);
	for(int i=1;i<=2*n-1;i++)
		SF("%d",&a[i]);
	eisiorti(a+1,a+2*n);
	dp[n][1][0]=1;
	for(int i=n;i>=2;i--){
		int al=(a[i-1]!=a[i]);
		int ar=(a[2*n-i+1]!=a[2*n-i]);
		for(int l=0;l<=2*n-1;l++)
			for(int r=0;r+l<=2*n-1;r++)
				if(dp[i][l][r]){
					for(int dl=1;dl<=l+al;dl++)
						(dp[i-1][l+al-dl+1][r+ar+(dl>1)]+=dp[i][l][r])%=MOD;	
					for(int dr=1;dr<=r+ar;dr++)
						(dp[i-1][l+al+1][r+ar-dr]+=dp[i][l][r])%=MOD;	
				}
	}
	int ans=0;
	for(int l=0;l<=2*n-1;l++)
		for(int r=0;r+l<=2*n-1;r++)
			(ans+=dp[1][l][r])%=MOD;
	PF("%d",ans);
}

좋은 웹페이지 즐겨찾기