wikioi 3130 CYD刷题(背包）-白红宇

wikioi 3130 CYD刷题(背包）

阅读量：6324 次

发布时间：2019-06-22

本文共 974 字，大约阅读时间需要 3 分钟。

下午，CYD要刷题了，已知CYD有N题可刷，但他只有M分钟的时间，而且他的智慧值为Q，也就是说他只能做出难度小于等于Q的题目。已知每题可得积分Ai，需花费时间Bi，难度为Ci，问CYD最多可得多少积分。

N M Q

Ai Bi Ci

可得最多积分

4 20 10

20 3 7

30 7 9

30 1 11

20 17 6

50

【样例解释】

选第1题和第2题

【数据范围】

对于33%的数据 N≤20 M≤100 Q≤20

对于100%的数据 N≤50 M≤500 Q≤100 AiBiCi≤300

1 #include
       
           2 #include
        
            3 #include
         
             4 #include
          
              5 #include
           
               6 #include
            
              7 #include
             
               8 #include
              
                9 #include
               
                 10 #include
                
                  11 #include
                  12 #include
                  
                    13 #include
                   
                     14 using namespace std;15 int f[10000],a[10000],b[100000],c[100000];16 int main()17 {18 int n,m,q;19 cin>>n>>m>>q;20 for(int i=0;i
                    
                     >a[i]>>b[i]>>c[i];23 if(c[i]>q)24 {25 a[i]=0;26 b[i]=0;27 }28 }29 for(int i=0;i
                     
                      b[i];j--)32 {33 f[j]=max(f[j],f[j-b[i]]+a[i]);34 }35 }36 cout<