首页 > 代码库 > hdu 4908 BestCoder Sequence【DP】
hdu 4908 BestCoder Sequence【DP】
题目链接 :http://acm.hdu.edu.cn/showproblem.php?pid=4908
题目大意:给出一个排列,一个m,求出这个排列的连续子序列中有多少个序列式以m为中位数。
由于是一个排列,不会出现重复的数字,记录一下m的位置index,然后以index为分界线,往左求出s[i](表示从i到index之间有多少大于m),b[i](表示从i到index之间有多少小于m),往右求出s[i](表示从index到i之间有多少大于m),b[i](表示从index到i之间有多少小于m)。我们需要求的是包含m在内的序列,如果这个序列满足(大于m的数的个数)等于(小于m的数的个数),那么这就是一个合法的序列;
设:
sl为数组中m左边的小于m的数的个数;
bl为数组中m左边的大于m的数的个数;
sr为数组中m右边的小于m的数的个数;
br为数组中m右边的大于m的数的个数;
那么需要满足sl+sr=bl+br =>sl-bl= - (sr-br) 令dp[i]=s[i]-b[i],当序列端点不在index处时,只要index两边的dp和相加为0的情况都是满足的,统计一下有多少吃即可;当序列端点在index处时,只要dp[i]等于0,那都是满足的,最后再相加起来就是答案了
代码:
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> using namespace std; #define N 40040 int sm[N],bi[N]; int dp[N]; int num[N]; int index; int main() { #ifndef ONLINE_JUDGE freopen("D:/in.txt","r",stdin); #endif // ONLINE_JUDGE int n,m; while(~scanf("%d%d",&n,&m)) { memset(sm,0,sizeof(sm)); memset(bi,0,sizeof(bi)); memset(dp,0,sizeof(dp)); scanf("%d",&num[0]); if(num[0]==m) index=0; else if(num[0]>m) { bi[0]=1; } else if(num[0]<m) sm[0]=1; for(int i=1;i<n;i++) { scanf("%d",&num[i]); if(num[i]==m) index=i; } for(int i=index-1;i>=0;i--) { if(i==index-1) { if(num[i]<m) sm[i]=1; else bi[i]=1; } else if(num[i]<m) { sm[i]=sm[i+1]+1; bi[i]=bi[i+1]; } else { sm[i]=sm[i+1]; bi[i]=bi[i+1]+1; } } for(int i=index+1;i<n;i++) { if(i==index+1) { if(num[i]<m) sm[i]=1; else bi[i]=1; } else if(num[i]<m) { sm[i]=sm[i-1]+1; bi[i]=bi[i-1]; } else { sm[i]=sm[i-1]; bi[i]=bi[i-1]+1; } } int ans=0; for(int i=0;i<n;i++) { dp[i]=sm[i]-bi[i]; if(!dp[i]) ans++; } sort(dp+index+1,dp+n); for(int i=index-1;i>=0;i--) { int temp=dp[i]; int lb=index,ub=n; while(ub-lb>1) { int mid=(ub+lb)/2; if(dp[mid]>(0-temp)) ub=mid; else lb=mid; } int a=ub; lb=index,ub=n; while(ub-lb>1) { int mid=(ub+lb)/2; if(dp[mid]>(0-temp)-1) ub=mid; else lb=mid; } int b=ub; ans+=(a-b); } printf("%d\n",ans); } return 0; }
需要sr为数组中m右边的小于m的数的个数;
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。