成人午夜视频全免费观看高清-秋霞福利视频一区二区三区-国产精品久久久久电影小说-亚洲不卡区三一区三区一区

方案dp。。-創(chuàng)新互聯(lián)

  最近經(jīng)常做到組合計(jì)數(shù)的題目,每當(dāng)看到這種題目第一反應(yīng)總是組合數(shù)學(xué),然后要用到排列組合公式,以及容斥原理之類的。。然后想啊想,最后還是不會(huì)做。。方案dp。。

  但是比賽完之后一看,竟然是dp。。例如前幾天的口號(hào)匹配求方案數(shù)的題目,今天的uva4656,以及hdu4248都是這種類型的題目。。

創(chuàng)新互聯(lián)公司致力于成都網(wǎng)站制作、成都做網(wǎng)站、外貿(mào)營(yíng)銷網(wǎng)站建設(shè),成都網(wǎng)站設(shè)計(jì),集團(tuán)網(wǎng)站建設(shè)等服務(wù)標(biāo)準(zhǔn)化,推過(guò)標(biāo)準(zhǔn)化降低中小企業(yè)的建站的成本,并持續(xù)提升建站的定制化服務(wù)水平進(jìn)行質(zhì)量交付,讓企業(yè)網(wǎng)站從市場(chǎng)競(jìng)爭(zhēng)中脫穎而出。 選擇創(chuàng)新互聯(lián)公司,就選擇了安全、穩(wěn)定、美觀的網(wǎng)站建設(shè)服務(wù)!

  說(shuō)說(shuō)uva4565吧。

  題意大概意思是:有N種紙牌,G給位置。。然后給定每種紙牌最少排幾張,求滿足的方案。

  這樣一來(lái)我們?cè)趺磩澐譅顟B(tài)呢?以位置?

  不,我們得用紙牌來(lái)劃分狀態(tài),并枚舉紙牌之前用了幾張

  那么用f[i][j]表示前I個(gè)紙牌已經(jīng)滿足題意,且總共放了j個(gè)位置的方案數(shù)。那么 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è)在剩下的G-k個(gè)里選擇位置就行了。。(這樣不會(huì)有問(wèn)題吧)

  hdu4248:

   這一題自己懶得寫了,轉(zhuǎn)自這個(gè)博客http://www.cnblogs.com/sweetsc/archive/2012/07/17/2595189.html

   我覺(jué)得寫得很不錯(cuò)!

   題意:有N種石頭,每種石頭有A1,A2....AN個(gè),現(xiàn)取出一些石頭組成序列,求可以組成多少種序列

   例如:3種:可以產(chǎn)生:B; G; M; BG; BM; GM; GB; MB; MG; BGM; BMG; GBM; GMB; MBG; MGB.

   我們采用動(dòng)態(tài)規(guī)劃的思想,劃分階段:按照石頭種類劃分階段。于是乎,咱們對(duì)于第i種石頭,相當(dāng)于之前石頭的顏色并不重要,借助高中數(shù)學(xué)插板法的思想,假如之前的i - 1 種石頭,拼出了長(zhǎng)    度為len,那么,相當(dāng)于有l(wèi)en + 1個(gè)空,咱們要放第 i 種石頭進(jìn)去,于是乎,轉(zhuǎn)化成了經(jīng)典問(wèn)題,我比較得意的總結(jié):

球和球盒和盒空盒情況數(shù)
有區(qū)別有區(qū)別有空盒m^n
有區(qū)別有區(qū)別無(wú)空盒M!s(n,m)
有區(qū)別無(wú)區(qū)別有空盒S(n,1)+s(n,2)+…+s(n,m),n>=m
S(n,1)+s(n,2)+…+s(n,n),n<=m
有區(qū)別無(wú)區(qū)別無(wú)空盒S(n,m)
無(wú)區(qū)別有區(qū)別有空盒C(n+m-1,n)
無(wú)區(qū)別有區(qū)別無(wú)空盒C(n-1,m-1)
無(wú)區(qū)別無(wú)區(qū)別有空盒DP
無(wú)區(qū)別無(wú)區(qū)別無(wú)空盒DP

   這里,第 i 種石頭互相沒(méi)有區(qū)別,len + 1個(gè)空有序,相當(dāng)于有區(qū)別,可以有空盒,于是,如果咱們從第 i 種中放put個(gè)進(jìn)去,情況數(shù)應(yīng)該是 C(put + len , put)

   于是設(shè)計(jì)狀態(tài):DP[i][j] 表示 用前 i 種石頭,排出長(zhǎng)度為 j 的可能數(shù)

   然后,狀態(tài)轉(zhuǎn)移的時(shí)候,枚舉在階段 i 放入put個(gè),DP[i + 1][j + put] += DP[i][j] * C(put + j, put) 即可

  附上自己奇丑無(wú)比的代碼:

   Uva4656

#include <iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<set>
#include<stack>
#include<cmath>
#include<vector>
#include<algorithm>
#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 <iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<set>
#include<stack>
#include<cmath>
#include<vector>
#include<algorithm>
#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);   
}

網(wǎng)頁(yè)標(biāo)題:方案dp。。-創(chuàng)新互聯(lián)
轉(zhuǎn)載注明:http://jinyejixie.com/article14/dpdede.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián),為您提供商城網(wǎng)站、小程序開(kāi)發(fā)品牌網(wǎng)站設(shè)計(jì)、標(biāo)簽優(yōu)化、外貿(mào)建站、域名注冊(cè)

廣告

聲明:本網(wǎng)站發(fā)布的內(nèi)容(圖片、視頻和文字)以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主,如果涉及侵權(quán)請(qǐng)盡快告知,我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如需處理請(qǐng)聯(lián)系客服。電話:028-86922220;郵箱:631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載,或轉(zhuǎn)載時(shí)需注明來(lái)源: 創(chuàng)新互聯(lián)

成都定制網(wǎng)站建設(shè)
乾安县| 外汇| 松潘县| 张家界市| 浪卡子县| 英吉沙县| 皮山县| 汽车| 塔城市| 泾川县| 沈丘县| 大田县| 新营市| 于都县| 台中县| 益阳市| 阳城县| 泌阳县| 桃园市| 额济纳旗| 游戏| 晋中市| 武乡县| 商都县| 龙南县| 平乐县| 阜康市| 鹿泉市| 绍兴市| 潞城市| 博客| 邢台市| 嘉善县| 安达市| 栖霞市| 株洲市| 柘荣县| 集安市| 甘肃省| 玉环县| 景宁|