当前位置:网站首页>Bzoj2431: [haoi2009] inverse pairwise sequence (DP, difference)

Bzoj2431: [haoi2009] inverse pairwise sequence (DP, difference)

2021-07-30 04:42:50 qq60ffc54300371

0072Vf1pgy1foxk76lzl8j31hc0u0dxk.jpg

Description

For a sequence {ai}, If there is i<j And ai>aj, Then we call ai And aj Is a pair of inverse logarithms . If for any one by 1~n It's made up of natural numbers
The sequence , It's easy to find out how many inverse logarithms there are . Then the inverse logarithm is k How many natural numbers are there ?

Input

The first line is two integers n,k.

Output

Write an integer , Indicates the number of qualified series , Because this number may be very large , You just output the number pair 10000 The result of finding the remainder .

Sample Input

4 1

Sample Output

3

Sample explanation :
The following 3 The reverse logarithms of all sequences are 1; Namely 1 2 4 3 ;1 3 2 4 ;2 1 3 4;
100% The data of n<=1000,k<=1000

Solution

In the computer room see After listening to all morning's World Final……
It's easy to design a state f[i][j] Express i The number is j The number of reverse order pairs
Suppose you put i-1 Number , It's time to put it in the first place i Number. .
Because the first i The number is the largest , So putting it to the far right of the queue can generate additional 0 In reverse order , Put it on the far left to generate additional i-1 individual
So put the first i The number can be increased 0~i-1 In reverse order
that f[i][j]=sigma(f[i-1][k]), among max(0,j-i+1)<=k<=j
It's easy to write a n^3 The violence of

Code

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 #define N (1000+10)
 5 using namespace std;
 6 int f[N][N],n,m;
 7 int main()
 8 {
 9     scanf("%d%d",&n,&m);
10     f[0][0]=1;
11     for (int i=1; i<=n; ++i)
12         for (int j=0; j<=m; ++j)
13             for (int k=max(0,j-i+1); k<=j; ++k)
14                 (f[i][j]+=f[i-1][k])%=10000;
15     printf("%d",f[n][m]);        
16 }

 

However n^3 Violence will never pass 1000 Of . However, there are 90.
We found that the third cycle of violence is just query f[i-1][] A section of ,
We just need one side DP While calculating the prefix and , Then you can optimize the third loop with prefix and .

 

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 #define N (1000+10)
 5 using namespace std;
 6 int f[N][N],sum[N][N],n,m;
 7 int main()
 8 {
 9     scanf("%d%d",&n,&m);
10     for (int i=0; i<=m; ++i) 
11         sum[0][i]=1;
12     for (int i=1; i<=n; ++i)
13         for (int j=0; j<=m; ++j)
14         {
15             f[i][j]=(j-i>=0) ? (sum[i-1][j]-sum[i-1][j-i]+10000)%10000 : sum[i-1][j];
16             sum[i][j]=(sum[i][j-1]+f[i][j])%10000;
17         }
18     printf("%d",f[n][m]);        
19 }

版权声明
本文为[qq60ffc54300371]所创,转载请带上原文链接,感谢
https://chowdera.com/2021/07/20210728100054495p.html

随机推荐