首页 > 代码库 > BZOJ 4798: [Ceoi2015]Calvinball championship
BZOJ 4798: [Ceoi2015]Calvinball championship
Description
将所有人分组，每个组的编号是这个组中名字字典序最小的人的排名，将所有人名字按字典序排名后，求这是第几大的序列。
Solution
DP.
\(f[i][j][0/1]\)表示当前第\(i\)位，最高位为\(j\)，是否顶格...
转移跟数位DP差不多...
因为我一开始把极限写成了\(mx\)...WA...
没滚数组...MLE...
取模太多被卡常...TLE...
新人求助，本地AC提交TLE...我发现本地\(0.2s 10^8\)
我也很绝望啊...
Code
#include <bits/stdc++.h>using namespace std;typedef long long LL;const int N = 10050;const int p = 1000007;inline void Add(int &x,LL y) { x=(x+y)%p; }int n,mx,cur;int a[N];int f[2][N][2];int main() { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); cur=mx=f[1][1][1]=1; for(int i=2;i<=n;i++) { cur^=1; for(int j=1;j<=i;j++) { f[cur][j][0]=f[cur][j][1]=0; Add(f[cur][j][0],(LL)f[cur^1][j][0]*j%p+f[cur^1][j-1][0]); if(j==mx) Add(f[cur][j][0],f[cur^1][j][1]*(a[i]-1)); }mx=max(mx,a[i]),f[cur][mx][1]=1;// for(int j=1;j<=n;j++) printf("%d,%d%c",f[cur][j][0],f[cur][j][1]," \n"[j==n]); } int ans=0; for(int i=1;i<=n;i++) Add(ans,f[cur][i][0]); printf("%d\n",(ans+1)%p); return 0;}
BZOJ 4798: [Ceoi2015]Calvinball championship
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。