@OceanEye5年前
12/13
01:50
@OceanEye7年前
07/13
14:46
神奇树状数组优化DP+组合数
思路很暴力……但是就是比较难连起来
第一步：
dp[i][j]表示枚举到第i位结尾且以第i位为结尾时 不下降子序列长度为j的情况数量
\( dp[i][j]=\sum_{k=1}^{j}(dp[i-1][k]) \)
第二步：
令 g[x] 表示所有长度为x的 不下降子序列 的数量
\( g[x]=\sum_{k=1}^{n}dp[k][x] \)
可以发现我们的ans和这个g[x]是由联系的
长度为x的 不下降子序列 的数量……和两个东西有关系
第一类—->从g[x+1]直接减少一位过来 第二类—->从非g[x+1]的过来 【参照定义理解】
第二类的数量是要记入答案的数量的
就稍微的暴力用n阶乘来做就好了，反正n不大
\( ans=\sum_{k=1}^{n}g[k]*(n-k)!-g[k+1]*g[k+1]*(n-k-1)!*(k+1) \)
以下代码
|
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 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 |
#include <cstdio> #include <algorithm> #include <cstring> #include <iostream> #include <cstdlib> #include <cmath> #define ll long long #define INF 1000000000 #define For(i,a,b) for(int i=a;i<=b;++i) #define p(x) ('0'<=x&&x<='9') char cc; int C; template <class T> void read( T &x ) { x=0; C=1; cc=getchar(); while(!p(cc)) { if(cc=='-') C=-1; cc=getchar(); } while(p(cc)) { x=x*10+cc-48; cc=getchar(); } x*=C; } #undef p using namespace std; #define N 2010 #define mod 1000000007LL #define lb(x) (x&-x) ll sum[N][N]; void add(int y,int pos,int val) { for(;pos<=N;pos+=lb(pos)) sum[y][pos]+=val,sum[y][pos]%=mod; } int query(int y,int pos) { static ll ret; for(ret=0;pos;pos-=lb(pos)) ret+=sum[y][pos]; return (int)(ret%mod); } #undef lb int dp[N][N],a[N],c[N],n; ll g[N],ans,l[N]; void init() { read(n); For(i,1,n) read(a[i]),c[i]=a[i]; sort(c+1,c+1+n); For(i,1,n) a[i]=lower_bound(c+1,c+1+n,a[i])-c; for(int i=1;i<=n;i++) { for(int j=i;j>=2;--j) { dp[i][j]=query(j-1,a[i]); add(j,a[i],dp[i][j]); } dp[i][1]=1; add(1,a[i],1); } } int main() { init(); For(i,1,n) for(int j=1;j<=n;j++) g[i]+=dp[j][i],g[i]%=mod; l[0]=1; ans+=g[n]; for(int i=n-1;i;i--) { l[n-i]=l[n-i-1]*(n-i)%mod; ans+=g[i]*l[n-i]%mod-(g[i+1]*l[n-i-1])%mod*(i+1)%mod; ans%=mod; } printf("%lld\n",(ans+mod)%mod); return 0; } |
BZOJ4361
@OceanEye7年前
05/29
21:46
dp[a][b][c][d][e][pre] = dp[a-1][b][c][d][e][1]*系数 + … + dp[a][b][c][d][e-1][5]*系数
其中a, b, c, d, e是能涂一块砖的颜色数，二，三……五
pre是上一次用的颜色是能涂pre块砖头的
因为上一次用的是能涂pre块砖头的，所以这一次涂色里能涂pre-1块砖头的颜色里有一种颜色不能用了
对应的系数就要-1
code
|
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 46 |
#include <cstdio> #include <algorithm> #include <cstring> #include <cstdlib> #include <cmath> #define ll long long #define INF 1000000000 #define MOD 1000000007 #define p(x) ('0'<=x&&x<='9') #define For(i,l,r) for(int i=l;i<=r;i++) char cc; int C; template <class T> void read( T &x ) { x=0; cc=getchar(); C=1; while(!p(cc)) { if(cc=='-') C=-1; cc=getchar(); } while(p(cc)) { x=x*10+cc-48; cc=getchar(); } x*=C; } using namespace std; ll dp[16][16][16][16][16][6]; #define NOW dp[a][b][c][d][e][pre] ll dfs(int a,int b,int c,int d,int e,int pre) { if(NOW) return NOW; if(!(a||b||c||d||e)) return NOW; if(a>0) NOW+=(a-(pre==2))*dfs(a-1,b,c,d,e,1); if(b>0) NOW+=(b-(pre==3))*dfs(a+1,b-1,c,d,e,2); if(c>0) NOW+=(c-(pre==4))*dfs(a,b+1,c-1,d,e,3); if(d>0) NOW+=(d-(pre==5))*dfs(a,b,c+1,d-1,e,4); if(e>0) NOW+=e*dfs(a,b,c,d+1,e-1,5); NOW%=MOD; return NOW; } int n,_,cnt[6]; int main() { for(int i=0;i<=5;i++) dp[0][0][0][0][0][i]=1; read(n); for(int i=1;i<=n;i++) read(_),cnt[_]++; printf("%lld",dfs(cnt[1],cnt[2],cnt[3],cnt[4],cnt[5],0)); return 0; } |
BZOJ1079
@OceanEye7年前
05/4
19:49
期望DP
题目要求维护三次方
所以要把二次和一次的期望也给维护了，接着考虑我们DP的含义是什么。
DP[3][i]=DP[3][i-1] + (增长幅度=x^3-(x-1)^3)*(增长概率=p[i])
上面那个三次方展开一下就可以做了
|
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 |
#include <cstdio> #include <algorithm> #include <cstring> #include <cstdlib> #include <iostream> #define ll long long #define INF 1000000000 #define p(x) ('0'<=x&&x<='9') char cc; int C; template <class T> void read( T &x ) { x=0; cc=getchar(); C=1; while(!p(cc)) { if(cc=='-') C=-1; cc=getchar(); } while(p(cc)) { x=x*10+cc-48; cc=getchar(); } x*=C; } using namespace std; #define N 100010 double dp[4][N],_; int main() { int n; read(n); for(int i=1;i<=n;i++) { scanf("%lf",&_); dp[1][i]=(dp[1][i-1]+1)*_; dp[2][i]=(dp[2][i-1]+2*dp[1][i-1]+1)*_; dp[3][i]=dp[3][i-1]+(3*dp[2][i-1]+3*dp[1][i-1]+1)*_; } printf("%.1lf",dp[3][n]); return 0; } |
BZOJ4318
@OceanEye7年前
05/3
18:56
期望DP
和班上的一个物理大佬一起搞了二十分钟吧……然后发现这个期望(R,B)只和(R-1,B)以及(R,B-1)相关
然后就一个for循环再用一下滚动数组就可以了
dp[r][b]=(dp[r][b-1]-1)*b/(r+b) + (dp[r-1][b]+1)*r/(r+b)
|
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 |
#include <cstdio> #include <algorithm> #include <cstring> #include <cstdlib> #include <iostream> #define ll long long #define INF 1000000000 #define p(x) ('0'<=x&&x<='9') char cc; int C; template <class T> void read( T &x ) { x=0; cc=getchar(); C=1; while(!p(cc)) { if(cc=='-') C=-1; cc=getchar(); } while(p(cc)) { x=x*10+cc-48; cc=getchar(); } x*=C; } using namespace std; int R,B; double dp[2][5050]; #define now i&1 #define pre now^1 int main() { read(R); read(B); for(int i=0;i<=B;i++) { for(int j=1;j<=R;j++) dp[now][j]=max(0.0,((dp[pre][j]-1)*((double)i/(i+j)))+((dp[now][j-1]+1)*((double)j/(i+j)))); } printf("%.6f",dp[B&1][R]-5e-7); return 0; } |