hdu 2583 permutation 동적 계획
3596 단어 동적 기획
Permutation plays a very important role in Combinatorics. For example ,1 2 3 4 5 and 1 3 5 4 2 are both 5-permutations. As everyone's known, the number of n-permutations is n!. According to their magnitude relatives ,if we insert the sumbols "<"or ">"between every pairs of consecutive numbers of a permutations,we can get the permutations with symbols. For example,1 2 3 4 5 can be changed to 1<2<3<4<5, 1 3 5 4 2 can be changed to 1<3<5>4>2. Now it's yout task to calculate the number of n-permutations with k"<"symbol. Maybe you don't like large numbers ,so you should just geve the result mod 2009.
Input
Input may contai multiple test cases. Each test case is a line contains two integers n and k .0
Output
The nonegative integer result mod 2007 on a line.
Sample Input
5 2
Sample Output
66
제목의 뜻은 대략 n의 전체 배열에서 작은 번호보다 큰 연결을 구하는 것이다. 그 중에서 작은 번호가 k개인 경우는 몇 가지가 있는가.ac 코드는% 2009이지 2007이 아닙니다.
분명히 n의 전체 배열은 n이다!dp 알고리즘 고려
상태 이동은DP(n,k)=dp(n-1,k)*(k+1)+dp(n-1)(k-1)*(n-k)
n은 n개의 숫자를 고려한 상태를 나타내고 k는 번호보다 작은 개수를 나타낸다.
먼저 특수한 상황을 만들고 서열 1, 2, 3, 4, 5, 모두 5개가 번호보다 작다. 만약에 내가 숫자 7을 넣으려면 나는 7가지 덧셈이 있고 단지 하나의 덧셈만 번호를 +1보다 작게 할 수 있다.
서열 a1a2a3a4a5.......a(n-1)는 모두 n-1개의 숫자가 있고 k개가 번호보다 작다. 그러면 내가 an을 넣으면 n가지의 덧셈이 있는데 그 중에서 번호보다 작은 것은 n-k종(번호보다 큰 위치에 붙이는 것)이 있고 다른 k+1종은 번호보다 작은 개수를 바꾸지 않는다.
#include<stdio.h>
int main()
{
int n,k,i,j,s;
int dp[111][111];
for(i=0;i<=101;i++)
{
dp[i][0]=1;
dp[0][i]=0;
}
while(scanf("%d%d",&n,&k)!=EOF)
{
for(i=1;i<=101;i++)
for(j=1;j<=101;j++)
{
dp[i][j]=(dp[i-1][j]*(j+1)+dp[i-1][j-1]*(i-j))%2009;
}
printf("%d
",dp[n][k]);
}
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
01 가방, 완전 가방, 다중 가방 dp(동적 기획 입문 dp)01 가방은 2진법으로 직접 표시할 수 있지만 데이터 양이 너무 많으면 시간을 초과하는 것이 폭력이다.01 가방의 사상은 바로 이 물품에 대해 내가 넣은 가치가 큰지 안 넣은 가치가 큰지 비교하여 방정식 f[i][v...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
