题目链接：https://www.lydsy.com/JudgeOnline/problem.php?id=3692
居然是NOI2018的80分的原题！
$f[i][j]$ 表示用了 $i$ 个数，最大的数为 $j$ 。
这样转移的时候是 $n^3$ 的，再维护一下 $i-1$ 的前缀和，这样转移的时候就是 $n^2$ 的了。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
#include<bits/stdc++.h> #define maxn 2020 #define mod 1000000007 using namespace std; inline int rd(){ int x=0,y=1;char c=getchar(); while(!isdigit(c)){if(c=='-')y=-y;c=getchar();} while(isdigit(c))x=x*10+c-'0',c=getchar(); return x*y; } int n,m; int f[maxn][maxn],sum[maxn]; inline void init(){ int Max=0; n=rd(),m=rd(); for(int i=1; i<=m; i++){ int x=rd(); Max=max(Max,x); } f[m][Max]=1; } inline void work(){ for(int i=m+1; i<=n; i++){ sum[0]=f[i-1][0]; for(int j=1; j<=n; j++)sum[j]=(sum[j-1]+f[i-1][j])%mod; for(int j=i; j<=n; j++){ f[i][j]=(f[i][j]+f[i-1][j])%mod; f[i][j]=(f[i][j]+sum[j-1])%mod; } } printf("%d\n",f[n][n]); } int main(){ init(); work(); return 0; } |
