意甲冠军：
集S它包括了很多间隔[l,r] 和1<=l<=r<=n f(S)个不相交的区间 问给出n和f(S) 有几种可能的S集合
思路：
dp好题 至于为啥是dp… 我仅仅能说是胖子大神教我的 - -b
定义 dp[i][j] 表示当n=i且f(S)=j时的S集合种类数 那么它能够通过dp[k][j-1]求得 j-1<=k<=i
能够这样理解转移
首先我们须要将 j-1 -> j 也就是加一个不相交的区间 [k+1,k+1] [k+1,k+2]...都能够 一共同拥有2^(i-k)-1种取法
上式-1由于不能全部这种区间全不取
为什么不是[k+2,...]的区间呢 由于我是遍历k的 k+2開始的区间在遍历到 k=k+1 的时候会算到
然后 我们能够随意取一些区间 这些区间一定和之前的相交
怎样一定相交呢 仅仅要让一端在k以内就好了 因此一共同拥有2^((i-k)*k)种取法
最后得出 dp[i][j] = sigma ( dp[k][j-1] * ( 2^(i - k) - 1 ) * ( 2^( (i - k) * k ) ) ) % mod
代码：
#include<cstdio> #include<cstring> #include<algorithm> #include<vector> using namespace std; #define N 510 #define LL __int64 #define mod 1000000007 LL dp[N][N],f[N*N]; int n,m; int main() { int i,j,k; scanf("%d%d",&n,&m); for(i=1,f[0]=1;i<N*N;i++) f[i]=(f[i-1]<<1)%mod; for(i=0;i<=n;i++) dp[i][0]=1; for(i=1;i<=n;i++) { for(j=1;j<=min(m,i);j++) { for(k=j-1;k<=i;k++) { dp[i][j]=(dp[i][j]+dp[k][j-1]*(f[i-k]-1)%mod*f[k*(i-k)]%mod)%mod; } } } printf("%I64d\n",dp[n][m]); return 0; }
版权声明：本文博主原创文章，博客，未经同意不得转载。
转载于:https://www.cnblogs.com/bhlsheji/p/4796932.html
相关资源：数据结构—成绩单生成器