网站建设教程 项目式,gateface做网站,凡科快图官方,网站建设网络营销平台 云搜系统P3205 [HNOI2010]合唱队
题意#xff1a;
有n个数#xff0c;然后插入队伍中#xff0c;如果队列当前为空#xff0c;则直接插入#xff0c;然后每次插入和上一次插入的比较#xff0c;如果大于#xff0c;插入当前队列的最右侧#xff0c;如果小于#xff0c;插入当…P3205 [HNOI2010]合唱队
题意
有n个数然后插入队伍中如果队列当前为空则直接插入然后每次插入和上一次插入的比较如果大于插入当前队列的最右侧如果小于插入当前队列的最左侧 现在给你一个插入后的队形问有多少种插入方式
题解
我们这样分析对于区间[l,r],最近一次插入的要么是第l位要么就是第r位 所以我们设f[i][j]表示可以排成理想队列中[i,j]区间且以最后一个排进去是第i人的初始队列种数。 设g[i][j]表示可以排成理想队列中[i,j]区间且以最后一个排进去是第j人的初始队列种数。 我们考虑f[i][j]第i位是本次刚插入的那上一个插入的位置可能是在第i1位或者是第j位第i1位的话就是上一次插入的是最左侧第j位的话就是上一次插入的是最右侧所以f[i][j]可以由f[i1][j]和g[i][j]得到前提是a[i]要小于a[i1]或者a[i]小于a[j],因为第i位插入到最左侧所以肯定是小于上次插入 同理对g[i][j]也可以推导出相应公式 最终为
代码:
#includebits/stdc.h
#define debug(a,b) printf(%s %d\n,a,b);
typedef long long ll;
using namespace std;inline int read(){int s0,w1;char chgetchar();while(ch0||ch9){if(ch-)w-1;chgetchar();}while(ch0ch9) ss*10ch-0,chgetchar();//s(s3)(s1)(ch^48);return s*w;
}
const int maxn1e39;
const int mod19650827;
int a[maxn];
int f[maxn][maxn],g[maxn][maxn];
int main()
{int n;cinn;for(int i1;in;i)cina[i];for(int i1;in;i)f[i][i]1;for(int len1;lenn;len){for(int i1;ilen-1n;i){int jilen-1;if(a[i]a[i1])//如果上一次进来的是第i1位 f[i][j]f[i1][j];if(a[i]a[j])//如果上一次进来的是第j位 f[i][j]g[i1][j];if(a[j]a[i])//如果上一次进来的是第 i位 g[i][j]f[i][j-1];if(a[j]a[j-1])//如果上一次进入的是第j-1位 g[i][j]g[i][j-1];f[i][j]%mod;g[i][j]%mod;}}cout(f[1][n]g[1][n])%mod; return 0;
}
