ZOJ-3929 Deque and Balls(DP+ 법칙 찾기)

2110 단어
제목의 대의: n개수, 각 수의 크기는 1~n 사이이다.n번을 조작하고 i번은 i번째 수를 양단 대열에 넣고 대열 양쪽에 놓을 확률은 같다.n회 조작한 후 양단 대기열에서 요소가xi>xi+1의 대수에 대한 기대를 충족시키고 출력된 데이터는 (기대*2^n)%mod입니다.
제목 분석: 정의 상태 dp(i)는 i회 조작 후의 상응하는 기대치를 나타낸다.상태 전환 방정식은 다음과 같습니다.
dp(i)=1/2*(dp(i-1)+k1)+1/2*(dp(i-1)+k2)(두 가지 경우 팀의 처음과 끝에 놓임) 중 k1은 a(i)보다 작은 원소가 a(i)와 인접할 수 있는 총 횟수를 나타내고, k2는 a(i)보다 큰 원소가 a(i)와 인접할 수 있는 총 횟수를 나타낸다.
합쳐서 얻을 수 있는 것은 dp(i)=dp(i-1)+(k1+k2)/2입니다. 출력된 데이터가'(기대*2^n)%mod'이기 때문에 dp(i)의 의미를 바꾸어 i부차적인 출력 결과를 조작하면 다음과 같습니다.
dp(i)=2*dp(i-1)+k1+k2=2*dp(i-1)+k(i-1)-num(a(i)), 그 중에서 k(i-1)는 전 i-1개수와 i개수가 인접할 수 있는 총 횟수를 나타내고,num(a(i))는 지금까지 a(i)와 같은 원소가 a(i)와 인접할 수 있는 총 횟수를 나타낸다.
k(i)와num(a(i)를 빠르게 구할 수 있는 법칙이 있다.만약 현재 i차 조작을 진행하고 있다면, 1, 2, 3...원소가 a(i)와 인접할 수 있는 횟수는 1, 1, 2, 4, 8...
상기 법칙을 표 f로 출력하기만 하면 k(i)와num(a)) 및num(a(i) 업데이트를 빠르게 찾을 수 있습니다.
 
코드는 다음과 같습니다.
# include
# include
# include
# include
# include
# include
# include
# include
# include
# include
# include
# include
using namespace std;
# define LL long long

const int N=1005;
const int INF=1000000000;
const LL oo=0x7fffffffffffffff;
const double eps=1e-10;
const int mod=1000000007;

int n;
LL sum[N*100];
LL f[N*100];
LL dp[N*100];
LL num[N*100];

void init()
{
	f[0]=f[1]=1;
	for(int i=2;i<=100000;++i)
		f[i]=(2*f[i-1])%mod;
	sum[0]=1;
	for(int i=1;i<=100000;++i)
		sum[i]=(f[i]+sum[i-1])%mod;
}

int main()
{
	init();
	int T;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d",&n);
		memset(num,0,sizeof(num));
		memset(dp,0,sizeof(dp));
		LL a;
		scanf("%lld",&a);
		dp[1]=0;
		num[a]=f[0]%mod;
		for(int i=2;i<=n;++i){
			scanf("%lld",&a);
			dp[i]=(2*dp[i-1]+sum[i-2]-num[a]+mod)%mod;
			num[a]=(num[a]+f[i-1])%mod;
		}
		printf("%lld
",(dp[n]*2)%mod);
	}
	return 0;
}

　　
전재 대상:https://www.cnblogs.com/20143605--pcx/p/5449610.html
파이톤으로 geometry processing 결과 보이기
PyODE 슬라이더를 이중으로 설정해 보십시오

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage