麻豆小视频在线观看_中文黄色一级片_久久久成人精品_成片免费观看视频大全_午夜精品久久久久久久99热浪潮_成人一区二区三区四区

首頁(yè) > 學(xué)院 > 開(kāi)發(fā)設(shè)計(jì) > 正文

藍(lán)橋杯第五屆 地宮取寶 (四維線性dp)

2019-11-10 20:13:50
字體:
來(lái)源:轉(zhuǎn)載
供稿:網(wǎng)友
  問(wèn)題描述  X 國(guó)王有一個(gè)地宮寶庫(kù)。是 n x m 個(gè)格子的矩陣。每個(gè)格子放一件寶貝。每個(gè)寶貝貼著價(jià)值標(biāo)簽。  地宮的入口在左上角,出口在右下角。  小明被帶到地宮的入口,國(guó)王要求他只能向右或向下行走。  走過(guò)某個(gè)格子時(shí),如果那個(gè)格子中的寶貝價(jià)值比小明手中任意寶貝價(jià)值都大,小明就可以拿起它(當(dāng)然,也可以不拿)。  當(dāng)小明走到出口時(shí),如果他手中的寶貝恰好是k件,則這些寶貝就可以送給小明。  請(qǐng)你幫小明算一算,在給定的局面下,他有多少種不同的行動(dòng)方案能獲得這k件寶貝。輸入格式  輸入一行3個(gè)整數(shù),用空格分開(kāi):n m k (1<=n,m<=50, 1<=k<=12)  接下來(lái)有 n 行數(shù)據(jù),每行有 m 個(gè)整數(shù) Ci (0<=Ci<=12)代表這個(gè)格子上的寶物的價(jià)值輸出格式  要求輸出一個(gè)整數(shù),表示正好取k個(gè)寶貝的行動(dòng)方案數(shù)。該數(shù)字可能很大,輸出它對(duì) 1000000007 取模的結(jié)果。樣例輸入2 2 21 22 1樣例輸出2樣例輸入2 3 21 2 32 1 5樣例輸出14題目分析:數(shù)據(jù)量不大,考慮用四維dp,dp[i][j][ma][num]表示到點(diǎn)(i,j)時(shí)最大值為ma取得了num個(gè)寶貝的方法數(shù),對(duì)于某個(gè)點(diǎn)如果它的寶藏值大于當(dāng)前最大值,則我們可以取也可以不取,否則我們只能不取,因此轉(zhuǎn)移方程:if(ma < val[i][j])  dp[i] [j] [ val[i][j] ] [num + 1] = (dp[i] [j] [ val[i][j] ] [num + 1] + dp[i - 1] [j] [ma] [num] + dp[i] [j - 1] [ma] [num]) % MOD //取dp[i] [j] [ma] [num] = (dp[i] [j] [ma] [num] +dp[i - 1] [j] [ma] [num] + dp[i] [j - 1] [ma] [num]) % MOD //不取 (這里沒(méi)有else,因?yàn)椴徽撐覀兡懿荒苋。覀兌伎梢赃x擇不取),最后我們只要累加dp[n][m][各最大值][k]的值即可,初始dp[1][1][val[1][1]][1] = 1第一個(gè)點(diǎn)取,dp[1][1][0][0]第一點(diǎn)不取這題還有兩個(gè)坑點(diǎn),第一:上述轉(zhuǎn)移方程要分成兩段寫(xiě),因?yàn)槭菍?duì)1e9+7取模,我們考慮最壞的情況,括號(hào)里的數(shù)就可能超int。第二:寶物的價(jià)值有可能是0,因?yàn)槌跏蓟癁?,因此混淆了空的點(diǎn)和價(jià)值為0的點(diǎn),因此我們讓每個(gè)寶藏的價(jià)值自增1
#include <cstdio>#include <cstring>#define MOD 1000000007int dp[55][55][15][15];int val[55][55];int main(){    int n, m, k;    scanf("%d %d %d", &n, &m, &k);    for(int i = 1; i <= n; i++)    {        for(int j = 1; j <= m; j++)        {            scanf("%d", &val[i][j]);            val[i][j] ++;        }    }    memset(dp, 0, sizeof(dp));    dp[1][1][val[1][1]][1] = 1;    dp[1][1][0][0] = 1;    for(int i = 1; i <= n; i++)    {        for(int j = 1; j <= m; j++)        {            if(i == 1 && j == 1)                continue;            for(int num = 0; num <= k; num++)            {                for(int ma = 0; ma <= 13; ma++)                {                    if(ma < val[i][j])                    {                        dp[i][j][val[i][j]][num + 1] = (dp[i][j][val[i][j]][num + 1] + dp[i - 1][j][ma][num]) % MOD;                        dp[i][j][val[i][j]][num + 1] = (dp[i][j][val[i][j]][num + 1] + dp[i][j - 1][ma][num]) % MOD;                        }                    dp[i][j][ma][num] = (dp[i][j][ma][num] + dp[i - 1][j][ma][num]) % MOD;                    dp[i][j][ma][num] = (dp[i][j][ma][num] + dp[i][j - 1][ma][num]) % MOD;                }            }        }    }    int ans = 0;    for(int i = 0; i < 13; i++)        ans = (ans + dp[n][m][i][k]) % MOD;    PRintf("%d/n", ans);}
發(fā)表評(píng)論 共有條評(píng)論
用戶名: 密碼:
驗(yàn)證碼: 匿名發(fā)表
主站蜘蛛池模板: 性爱免费在线视频 | 国产一区毛片 | asian超清日本肉体pics | 97久久精品一区二区三区观看 | 欧美一级片一区 | 91久久国产 | 国产成人高清成人av片在线看 | 国产人成精品综合欧美成人 | 久久6国产 | 91国内精品久久久久免费影院 | 福利在线免费视频 | 欧美日韩国产一区二区三区在线观看 | 成人免费一区二区三区在线观看 | 久久亚洲一区二区三区成人国产 | 久久99综合 | 免费观看一级黄色片 | 亚洲影院在线 | 日本黄色一级电影 | 欧美成人午夜精品久久久 | 亚洲精品免费播放 | 国产chinesehd精品91 | 99在线啪 | 日韩黄网站 | 色吧综合网 | 一色桃子av大全在线播放 | 亚洲爱爱网站 | 男人的天堂视频网站 | 久久超| 狠狠婷婷综合久久久久久妖精 | 黑人操穴 | 中国黄色一级生活片 | 妇子乱av一区二区三区 | 深夜影院一级毛片 | 国产成人精品区 | av手机在线免费播放 | 美女91视频 | 中文字幕在线视频网站 | 日韩大片在线永久观看视频网站免费 | 国产69精品久久久久9999不卡免费 | 欧美成年人视频在线观看 | 人人做人人看 |