洛谷 P1964 【mc生存】卖东西-白红宇

洛谷 P1964 【mc生存】卖东西

阅读量：5059 次

发布时间：2019-06-12

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

题目背景

服务器好好玩

题目描述

lcy0x1去服务器的系统商店卖东西。

一个人的背包有21格。

一开始他的背包里有m件不同的物品（不能卖）。

他要卖n种物品，每种物品有ai件,价值bi,一格可以放ci个，

名字sti（0<sti的长度<100)

相同的物品可以放同一格(只要没放满）。

问他跑一次最多能卖多少钱。

输入输出格式

输入格式：

第一行m,n(0<=m<=21,0<=n<=100)；

下面n行 ai,bi,ci,sti(0<=ai<=1344,0<=bi<=10000,0<ci<=64)；

输出格式：

最多卖的钱s(0<=s<=1000000)；

输入输出样例

输入样例#1：

20 363 1 64 yinshifen1 10 1 men1 1 64 yinshifen

输出样例#1：

说明

多重背包

搜索0分！！！

强大的数据

思路：预处理+01背包。

#include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               //用STL的map的头文件using namespace std;int dp[30],w[150000];map
                
                 a,b,c;map
                 
                  d;string s[105];int main(){ int n,m,l,i,j,k,maxi=0; cin>>m>>n; m=21-m; for(i=1;i<=n;i++){ cin>>l>>j>>k; cin>>s[i]; a[s[i]]+=l; b[s[i]]=j; c[s[i]]=k; } k=0; for(i=1;i<=n;i++){ if(d[s[i]]==0){ d[s[i]]=1; while(a[s[i]]>=c[s[i]]){ w[++k]=c[s[i]]*b[s[i]]; a[s[i]]-=c[s[i]]; } if(a[s[i]]) w[++k]=a[s[i]]*b[s[i]]; } } for(i=1;i<=k;i++){ for(j=m;j>=1;j--){ dp[j]=max(dp[j],dp[j-1]+w[i]); maxi=max(maxi,dp[j]); } } cout<
                  
                   <