【题解】洛谷P3205【HNOI2010】合唱队

洛谷 P3205：https://www.luogu.org/problemnew/show/P3205

复习区间DPing

思路

把理想队列拆分成

第一个和后面几个 划分成求后面几个的理想队列最后一个和前面几个 划分成求前面几个的理想队列

        样例：1701 1702 1703 1704

把1701拿出来 求1702 1703 1704的理想队列把1704拿出来 求1701 1702 1703的理想队列

因此需要两个数组来划分阶段

f[i][j]为可以排成理想队列中[i,j]区间 且以最后一个排进去是第i人的初始队列种数。

g[i][j]为可以排成理想队列中[i,j]区间 且以最后一个排进去是第j人的初始队列种数。

就可以得出数组f的两种情况：

前一个排进去的人是i+1 当前人插到最左边

if(q[i]<q[i+1]) f[i][j]=(f[i][j]+f[i+1][j])%MOD;

前一个排进去的人是j 当前人插到最左边

if(q[i]<q[j]) f[i][j]=(f[i][j]+g[i+1][j])%MOD;

同理可得数组g的两种情况：

前一个排进去的人是i 当前人插到最右边

if(q[i]<q[j]) g[i][j]=(g[i][j]+f[i][j-1])%MOD;

前一个排进去的人是j-1 当前人插到最右边

if(q[j-1]<q[j]) g[i][j]=(g[i][j]+g[i][j-1])%MOD;

答案存在f[1][n]+g[1][n]中

代码

#include<iostream> #include<cstdio> using namespace std; #define maxn 1010 #define MOD 19650827 int n; int q[maxn]; int f[maxn][maxn],g[maxn][maxn]; int main() { scanf("%d",&n); for(int i=1;i<=n;i++) cin>>q[i]; for(int i=1;i<=n;i++) f[i][i]=1;//初始化本身为一种 for(int i=n-1;i>=1;i--) for(int j=i+1;j<=n;j++) { if(q[i]<q[i+1])//i+1是从队首取的所以+f[i+1][j] f[i][j]=(f[i][j]+f[i+1][j])%MOD; if(q[i]<q[j])//j是从队尾取的所以+g[i+1][j] f[i][j]=(f[i][j]+g[i+1][j])%MOD; if(q[i]<q[j])//i是从队首取的所以+f[i][j-1] g[i][j]=(g[i][j]+f[i][j-1])%MOD; if(q[j-1]<q[j])//j-1是从队尾取的所以+g[i][j-1] g[i][j]=(g[i][j]+g[i][j-1])%MOD; } printf("%d",(f[1][n]+g[1][n])%MOD); } View Code

 

转载于:https://www.cnblogs.com/BrokenString/p/9478343.html

相关资源：JAVA上百实例源码以及开源项目