P3205 [HNOI2010]合唱队

终于可以水博客了!!

这sb题居然让我这垃圾想了这么长时间,结果一遍过了。

P3205 [HNOI2010]合唱队

原题

吐槽

这题老师~~(学姐)~~讲的时候,一眼看上去,真的好难啊!

但是仔细一想,好像真的对不起这蓝色的难度了。

真是个sb题啊,亏我想了那么久!!!!

好了,不bibi了,看题。

我们都知道这是个区间DP,那么我们就直接谈谈思路吧!

思路

我们暂且将给出的数据中的数列叫做理想数列。

例如样例中的1701 1702 1703 1704便是一个理想数列。

我们用两个数组来处理,

fi,jf_{i,j}表示在理想数列中的[i,j][i,j]这个区间,最后一个被加入的数是ii的情况数。

gi,jg_{i,j}表示在理想数列中的[i,j][i,j]这个区间,最后一个被加入的数是jj的情况数。

因此,可以分别得到两种情况:

对于f数组

  1. 前一个排进去的人是i+1
  2. 前一个排进去的人是j

得到代码:

1
2
if(a[i]<a[i+1]) (f[i][j]+=f[i+1][j])%=mod;
if(a[i]<a[j]) (f[i][j]+=g[i+1][j])%=mod;

对于g数组

  1. 前一个排进去的人是i
  2. 前一个排进去的人是j-1

得到代码

1
2
if(a[j]>a[i]) (g[i][j]+=f[i][j-1])%=mod;
if(a[j]>a[j-1]) (g[i][j]+=g[i][j-1])%=mod;

答案便是f[1][n]+g[1][n]

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<cstdio>

const int maxn=1e3+10;
const int mod=19650827;

int n,a[maxn],f[maxn][maxn],g[maxn][maxn];

inline int read(){
char ch=getchar();int f=1,r=0;
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch<='9'&&ch>='0'){r=r*10+ch-'0';ch=getchar();}
return f*r;
}

int main(){
n=read();
for(register int i=1;i<=n;i++){
a[i]=read();
f[i][i]=1;//dp: [i,i]区间中只有一个人,情况只有一种
}
for(register int i=n;i>=1;i--){
for(register int j=i+1;j<=n;j++){
if(a[i]<a[i+1]) (f[i][j]+=f[i+1][j])%=mod;
if(a[i]<a[j]) (f[i][j]+=g[i+1][j])%=mod;
if(a[j]>a[i]) (g[i][j]+=f[i][j-1])%=mod;
if(a[j]>a[j-1]) (g[i][j]+=g[i][j-1])%=mod;
}
}
printf("%d\n",(f[1][n]+g[1][n])%mod);
return 0;
}
文章作者: Langlangago
文章链接: https://langlangago.xyz/2019/08/17/P3205 [HNOI2010]合唱队/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Langlangago's blog

评论