国产探花免费观看_亚洲丰满少妇自慰呻吟_97日韩有码在线_资源在线日韩欧美_一区二区精品毛片,辰东完美世界有声小说,欢乐颂第一季,yy玄幻小说排行榜完本

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

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

2019-11-10 23:46:01
字體:
供稿:網(wǎng)友
  問題描述  X 國王有一個(gè)地宮寶庫。是 n x m 個(gè)格子的矩陣。每個(gè)格子放一件寶貝。每個(gè)寶貝貼著價(jià)值標(biāo)簽。  地宮的入口在左上角,出口在右下角。  小明被帶到地宮的入口,國王要求他只能向右或向下行走。  走過某個(gè)格子時(shí),如果那個(gè)格子中的寶貝價(jià)值比小明手中任意寶貝價(jià)值都大,小明就可以拿起它(當(dāng)然,也可以不拿)。  當(dāng)小明走到出口時(shí),如果他手中的寶貝恰好是k件,則這些寶貝就可以送給小明。  請你幫小明算一算,在給定的局面下,他有多少種不同的行動(dòng)方案能獲得這k件寶貝。輸入格式  輸入一行3個(gè)整數(shù),用空格分開:n m k (1<=n,m<=50, 1<=k<=12)  接下來有 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 //不取 (這里沒有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)移方程要分成兩段寫,因?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ā)表
主站蜘蛛池模板: 龙州县| 满城县| 蛟河市| 赞皇县| 阜宁县| 昌乐县| 山阴县| 桓台县| 华阴市| 高州市| 兰坪| 桐城市| 长沙市| 汉中市| 博兴县| 新邵县| 泰和县| 浑源县| 兴城市| 乳源| 新津县| 北票市| 邵东县| 湾仔区| 华安县| 大英县| 平远县| 山丹县| 宁远县| 吴堡县| 乃东县| 繁峙县| 册亨县| 清新县| 北宁市| 三穗县| 独山县| 定边县| 绥棱县| 永昌县| 股票|