• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            隨筆-65  評論-6  文章-0  trackbacks-0
             1 /*
             2 Author:    Leo.W
             3 Descriptipn:    一個二維背包的問題,給定升級上限經驗n,在忍耐力和殺怪數上限為m與s的情況下,
             4                 面對所列的k種怪物,每種所獲經驗a[],消耗忍耐b[]。在能升級的情況下保留的最多
             5                 忍耐值。不能升級則輸出-1.
             6 How to Do:    加一維消耗,作完全背包,每種怪的數量是無限的。
             7   */
             8 #include <stdio.h>
             9 #include <iostream>
            10 #include <string.h>
            11 using namespace std;
            12 #define MAXSIZE 102
            13 int DP[MAXSIZE][MAXSIZE];
            14 int a[MAXSIZE];
            15 int b[MAXSIZE];
            16 int main(){
            17     //freopen("in.txt","r",stdin);
            18     int N,M,K,S;
            19     while (scanf("%d%d%d%d",&N,&M,&K,&S)!=EOF){
            20         int i,j,k;
            21         for(i=0;i<K;i++)    scanf("%d%d",&a[i],&b[i]);
            22         memset(DP,0,sizeof(DP));
            23         for(i=1;i<=M;i++){
            24             for(j=1;j<=S;j++){
            25                 for(k=0;k<K;k++){
            26                     if(i-b[k]>=0){
            27                         if (DP[i-b[k]][j-1]+a[k]>DP[i][j])    
            28                             DP[i][j]=DP[i-b[k]][j-1]+a[k];    
            29                     }
            30                 }
            31             }
            32             if (DP[i][S]>=N)//當滿足升級 即跳出
            33                 break;
            34         }
            35         if(i>M)    printf("-1\n");
            36         else printf("%d\n",M-i);
            37     }
            38 
            39     return 0;
            40 } 
            41 
            posted on 2012-03-12 22:45 Leo.W 閱讀(170) 評論(0)  編輯 收藏 引用
            狠狠色噜噜色狠狠狠综合久久| 伊人久久无码精品中文字幕| 99麻豆久久久国产精品免费 | 狠狠色丁香婷婷久久综合五月| 久久久久久青草大香综合精品| 欧美日韩精品久久久久| 91精品国产高清91久久久久久| 久久久久亚洲精品天堂久久久久久| 一极黄色视频久久网站| 97久久久久人妻精品专区| 亚洲精品久久久www| 日本三级久久网| 久久精品中文无码资源站| 精品久久久久久久久久中文字幕 | 久久久久九国产精品| 久久国产精品无码HDAV| 亚洲精品午夜国产va久久| 国产成人精品久久综合| 久久亚洲欧美国产精品| 香蕉久久久久久狠狠色| 久久精品亚洲福利| 久久综合九色综合精品| 国产精品欧美久久久天天影视| 精品久久亚洲中文无码| 亚洲欧美日韩精品久久亚洲区 | jizzjizz国产精品久久| 久久人人爽人人爽人人av东京热 | 国产精品国色综合久久| 亚洲∧v久久久无码精品| 99久久国产精品免费一区二区| 中文字幕精品久久| 国产99久久久国产精品小说| 久久久这里只有精品加勒比| 久久久精品国产| 伊人久久大香线蕉av不卡 | 欧美与黑人午夜性猛交久久久 | 久久国产精品一区二区| 国产精品久久久久久久久免费| 久久精品国产69国产精品亚洲| 精品亚洲综合久久中文字幕| 亚洲精品高清久久|