大橙子网站建设,新征程启航

为企业提供网站建设、域名注册、服务器等服务

方案dp。。-创新互联

  最近经常做到组合计数的题目,每当看到这种题目第一反应总是组合数学,然后要用到排列组合公式,以及容斥原理之类的。。然后想啊想,最后还是不会做。。方案dp。。

  但是比赛完之后一看,竟然是dp。。例如前几天的口号匹配求方案数的题目,今天的uva4656,以及hdu4248都是这种类型的题目。。

创新互联公司致力于成都网站制作、成都做网站、外贸营销网站建设,成都网站设计,集团网站建设等服务标准化,推过标准化降低中小企业的建站的成本,并持续提升建站的定制化服务水平进行质量交付,让企业网站从市场竞争中脱颖而出。 选择创新互联公司,就选择了安全、稳定、美观的网站建设服务!

  说说uva4565吧。

  题意大概意思是:有N种纸牌,G给位置。。然后给定每种纸牌最少排几张,求满足的方案。

  这样一来我们怎么划分状态呢?以位置?

  不,我们得用纸牌来划分状态,并枚举纸牌之前用了几张

  那么用f[i][j]表示前I个纸牌已经满足题意,且总共放了j个位置的方案数。那么 f[i][j] = sigma(f[i-1][k] * c[G - k][j - k]){j - k >= a[i]}

  至于为什么是 f[i-1][k] * c[G - k][j - k],我们可以这样理解:

       反正总的位置固定,选取的j-k个在剩下的G-k个里选择位置就行了。。(这样不会有问题吧)

  hdu4248:

   这一题自己懒得写了,转自这个博客http://www.cnblogs.com/sweetsc/archive/2012/07/17/2595189.html

   我觉得写得很不错!

   题意:有N种石头,每种石头有A1,A2....AN个,现取出一些石头组成序列,求可以组成多少种序列

   例如:3种:可以产生:B; G; M; BG; BM; GM; GB; MB; MG; BGM; BMG; GBM; GMB; MBG; MGB.

   我们采用动态规划的思想,划分阶段:按照石头种类划分阶段。于是乎,咱们对于第i种石头,相当于之前石头的颜色并不重要,借助高中数学插板法的思想,假如之前的i - 1 种石头,拼出了长    度为len,那么,相当于有len + 1个空,咱们要放第 i 种石头进去,于是乎,转化成了经典问题,我比较得意的总结:

球和球盒和盒空盒情况数
有区别有区别有空盒m^n
有区别有区别无空盒M!s(n,m)
有区别无区别有空盒S(n,1)+s(n,2)+…+s(n,m),n>=m
S(n,1)+s(n,2)+…+s(n,n),n<=m
有区别无区别无空盒S(n,m)
无区别有区别有空盒C(n+m-1,n)
无区别有区别无空盒C(n-1,m-1)
无区别无区别有空盒DP
无区别无区别无空盒DP

   这里,第 i 种石头互相没有区别,len + 1个空有序,相当于有区别,可以有空盒,于是,如果咱们从第 i 种中放put个进去,情况数应该是 C(put + len , put)

   于是设计状态:DP[i][j] 表示 用前 i 种石头,排出长度为 j 的可能数

   然后,状态转移的时候,枚举在阶段 i 放入put个,DP[i + 1][j + put] += DP[i][j] * C(put + j, put) 即可

  附上自己奇丑无比的代码:

   Uva4656

#include 
#include
#include
#include
#include
#include
#include
#include
#include
#define MXN 50100
#define Inf 101010
#define M0(a) memset(a, 0, sizeof(a))
using namespace std;
double c[36][36], f[36][36];
int a[50], sum[50];
int n, m;
void init(){
     M0(c);
for (int i = 0; i <= 33; ++i)
        c[i][0] = 1;
for (int i = 1; i <= 33; ++i)
for (int j = 1; j <= i; ++j)
          c[i][j]= c[i-1][j] + c[i-1][j-1];
}

void solve(){
    M0(sum);
    M0(f);
    scanf("%d%d", &n, &m); 
for (int i = 1; i <= m; ++i){
        scanf("%d", &a[i]);
        sum[i]= sum[i-1] + a[i];
    }
    f[0][0] = 1;
for (int i = 1; i <= m; ++i)
for (int j = sum[i]; j <= n; ++j){
for (int k = a[i]; k <= j; ++k)
             f[i][j]+= f[i-1][j-k] * c[n - j + k][k];
       }
for (int i = 1; i <= n; ++i)
      f[m][n]/= m;
    printf("%.6lf
", f[m][n] * 100.00);
}

int main(){
//   freopen("a.in", "r", stdin);
//   freopen("a.out","w", stdout);   int T, cas = 0;
     scanf("%d", &T);
     init();
for (int i = 1; i <= T; ++i){
          printf("Case #%d:", i);
          solve(); 
     }

//    fclose(stdin); fclose(stdout);}

hdu4248

#include 
#include
#include
#include
#include
#include
#include
#include
#include
#define MXN 50100
#define Inf 101010
#define P 1000000007
#define M0(a) memset(a, 0, sizeof(a))
using namespace std;
int  c[10100][102];
long long  f[102][10100];
int n, a[110], m, sum[110];

void init(){
for (int i = 0; i <= 10010; ++i) 
       c[i][0] = 1;
for (int i = 1; i <= 10010; ++i)
for (int j = 1; j <= 101 && j <= i; ++j)
         c[i][j]= (c[i-1][j] + c[i-1][j-1]) % P;
}

void solve(){
      m= 0;
      M0(f);
      M0(sum);
for (int i = 1; i <= n; ++i){
          scanf("%d", &a[i]);  
           m+= a[i];
           sum[i]= m;  
      }  
      f[0][0] = 1;
long long ans = 0;
for (int i = 1; i <= n; ++i)
for (int j = 0; j <= sum[i]; ++j){
for (int k = 0; k <= a[i]; ++k){
if (k > j) break;
                 f[i][j]= (f[i][j] + f[i-1][j-k] * c[j][k]) % P;
             }
if (i == n && j) ans =  (ans + f[i][j]) % P;
         }
      printf("%I64d
", ans);
}

int main(){
//freopen("a.in", "r", stdin);
//    freopen("a.out","w", stdout);   int T, cas = 0;
     init();
while (scanf("%d", &n) != EOF){
          printf("Case %d:", ++cas);
          solve(); 
     }

     fclose(stdin); fclose(stdout);   
}

分享文章:方案dp。。-创新互联
本文来源:http://dzwzjz.com/article/dpdede.html
在线咨询
服务热线
服务热线:028-86922220
TOP