网站开发工程师招聘,用vs2010做免费网站模板下载地址,室内设计公司logo,龙岗网站开发Description 为了在即将到来的晚会上有吏好的演出效果#xff0c;作为AAA合唱队负责人的小A需要将合唱队的人根据他们的身高排出一个队形。假定合唱队一共N个人#xff0c;第i个人的身髙为Hi米(1000Hi2000),并已知任何两个人的身高都不同。假定最终排出的队形是A 个人…Description 为了在即将到来的晚会上有吏好的演出效果作为AAA合唱队负责人的小A需要将合唱队的人根据他们的身高排出一个队形。假定合唱队一共N个人第i个人的身髙为Hi米(1000Hi2000),并已知任何两个人的身高都不同。假定最终排出的队形是A 个人站成一排为了简化问题小A想出了如下排队的方式他让所有的人先按任意顺序站成一个初始队形然后从左到右按以下原则依次将每个人插入最终棑出的队形中 -第一个人直接插入空的当前队形中。 -对从第二个人开始的每个人如果他比前面那个人髙(H较大)那么将他插入当前队形的最石边。如果他比前面那个人矮(H较小)那么将他插入当前队形的最左边。 当N个人全部插入当前队形后便获得最终排出的队形。 例如有6个人站成一个初始队形身卨依次为1850、1900、1700、1650、1800和1750, 那么小A会按以下步骤获得最终排出的队形 1850 1850 , 1900 因为 1900 18501700, 1850, 1900 因为 1700 19001650 . 1700, 1850, 1900 因为 1650 17001650 , 1700, 1850, 1900, 1800 因为 1800 16501750 1650, 17001850, 1900, 1800 因为 1750 1800 因此最终排出的队形是 1750165017001850, 19001800 小A心中有一个理想队形他想知道多少种初始队形可以获得理想的队形solution 正解DP 简单题啊赋初值很坑花了有点久 因为最终队形的产生一定是左右逐渐扩展的所以考虑区间DP. 最后一个加入的不是区间的左端点就是右端点我们加入状态考虑即可 设 \(dp[i][j][0/1]\)表示区间 \([i,j]\)已经形成理想队列最后一个加入的为左/右端点的方案数 注意赋初值时一定要直接给长度为2的区间赋值 #include algorithm
#include iostream
#include cstdlib
#include cstring
#include cstdio
#include cmath
#define RG register
using namespace std;
const int N1005,mod19650827;
int n,a[N],dp[N][N][2];
inline void add(RG int x,int y){xy;if(xmod)x-mod;}
void work()
{scanf(%d,n);for(int i1;in;i)scanf(%d,a[i]);for(int i1;in;i){dp[i][i1][0]a[i]a[i1];dp[i][i1][1]a[i]a[i1];}for(int k2;kn;k){for(int i1;ik-1n;i){RG int jik-1;if(i1){if(a[i-1]a[i])add(dp[i-1][j][0],dp[i][j][0]);if(a[i-1]a[j])add(dp[i-1][j][0],dp[i][j][1]);}if(jn){if(a[j1]a[j])add(dp[i][j1][1],dp[i][j][1]);if(a[j1]a[i])add(dp[i][j1][1],dp[i][j][0]);}}}printf(%d\n,(dp[1][n][0]dp[1][n][1])%mod);
}int main(){work();return 0;
}转载于:https://www.cnblogs.com/Yuzao/p/7966643.html
