2016年9月13日 星期二

ZJ d645 輪下亡魂

http://zerojudge.tw/ShowProblem?problemid=d645

大概是我寫出的第二題DP吧XDD
第一題是d652 前天寫出來的

或許這在大家眼裡都是水題XDDD
不過我決定紀錄一下(#
這是一個沒有寫過普通背包就寫有無限有限背包問題的故事(#

總之開一個當容量為多少的時候最大飽足感的陣列
然後對於每種食物去跑一次每種容量再跑一圈每種數量(工弎洨
然後如果是無限的飼料就跑到容量用完就好(?

算了我還是直接上code好了=w=
表達能力真的有點((((



 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include<bits/stdc++.h>
using namespace std;

int n,c,v[1004],w[1004],t[1004],cs[1004];


int dp(){
    cs[0]=0;
    for(int i=1;i<=n;i++){
        for(int j=c;j>=w[i];j--){
            for(int k=0;j-w[i]*k>=0 && (k<=t[i] || t[i]==-1);k++){
                cs[j] = max(cs[j], cs[j-w[i]*k]+v[i]*k);
            }
        }
    }
    return cs[c];
}

int main(){
    cin>>n>>c;
    for(int i=1;i<=n;i++){
        cin>>v[i]>>w[i]>>t[i];
    }

    cout<<dp()<<endl;
}

發現出乎意料的短(?
張貼者： 於

3 則留言:

訂閱： 張貼留言 (Atom)