[BZOJ3622] 더 이상 무서울 게 없어. (용척원리+DP)
4603 단어 DP 어렵다.BZOJ머리를 돌릴 수 없는 용척의 원리
=== ===
여기에 전송문을 놓다
=== ===
문제풀이
우선 요구를 충족시키려면 알약보다 사탕이 몇 조 커야 하는지 계산할 수 있다. 바로 (n+k)/2이다.n+k가 2를 정제하지 못하면 무해하다고 판단한다.K=(n+k)2를 설정합니다.직접 구하는 것은 쉽지 않다. 직접 구하면 한 K조의 A가 B보다 크고 나머지 A가 B보다 크지 않다는 것을 보증해야 하기 때문이다.그러면 K조 A가 B보다 큰 것을 먼저 구하면 DP가 된다.먼저 A와 B를 각각 정렬한 다음에 f[i][j]를 설정하면 A조의 첫 번째 숫자를 나타낸다. A가 B보다 큰 것은 j조가 있다.이렇게 하면 두 개의 수조가 질서정연하기 때문에 A가 B보다 큰 접두사를 쉽게 포지셔닝할 수 있다. 이 접두사를 설정하면 모두 p개의 수가 있는데 그 안에 처음에 j개를 선택했고 p-j개를 선택하지 않았기 때문에 f[i+1]를 전달할 때 다음과 같다.
f[i+1][j+1]={f[i][j+1], A조의 i+1 숫자가 B조의 숫자보다 크지 않도록 강요하지 않는다. f[i][j]∗(p-j), A조의 i+1 숫자가 B조의 어떤 숫자보다 크다.
그러면 마지막 f[n][i]는 i조수를 선정하여 A가 B보다 큰 방안을 강행하도록 하는 것이다.나머지 n-i개의 숫자는 마음대로 놓을 수 있다. 그러면 적어도 k조 A가 B보다 큰 방안 수를 얻을 수 있다.그러나 아무렇게나 놓은 숫자도 A가 B보다 큰 상황을 초래할 수 있으므로 용납해야 한다.
∑i=knf[n][i]∗C(i,k)∗(−1)i−k .
코드
#include
");return 0;}
k=(n+k)/2;f[0][0]=1;
get_C(n);mul[0]=1;
for (int i=1;i<=n;i++) mul[i]=mul[i-1]*i%Mod;
for (int i=1;i<=n;i++) scanf("%d",&a[i]);
for (int i=1;i<=n;i++) scanf("%d",&b[i]);
sort(a+1,a+n+1);sort(b+1,b+n+1);
for (int i=0,p=0;i<=n;i++){
while (p1]1]) ++p;
for (int j=0;j<=i;j++)
if (f[i][j]!=0){
f[i+1][j]=(f[i+1][j]+f[i][j])%Mod;
if (p-j>=0)
f[i+1][j+1]=(f[i+1][j+1]+f[i][j]*(long long)(p-j)%Mod)%Mod;
}
}
for (int i=0;i<=n;i++) f[n][i]=f[n][i]*mul[n-i]%Mod;
for (int i=k,dlt=1;i<=n;i++,dlt=-dlt)
Ans=(Ans+dlt*C[i][k]*f[n][i]%Mod)%Mod;
Ans=(Ans+Mod)%Mod;
printf("%I64d",Ans);
return 0;
} 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
BZOJ1864 [Zjoi2006] 트리플 트리 DP트리 DP 입문 문제로 여러 갈래 나무가 두 갈래 나무를 돌릴 필요가 없다. f(i, j)로 i번째 노드가 j색을 칠할 때 하위 트리의 정점은 녹색이 가장 많은 개수를 나타내고 fs(i, j)는 가장 적은 개수를 나...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
