U65320 Oak的预算方案-白红宇

U65320 Oak的预算方案

阅读量：5290 次

发布时间：2019-06-14

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

如有乱码，请。

题目背景

早在 $(({-1})^{2k(k\in N)}-\dfrac{1}{e^{i\pi}})((−1)2k(k∈N)−eiπ1) 年前，$

题目描述

金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间金明自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过

| 工作椅 |

如果要买归类为附件的物品，必须先买该附件所属的主件。附件不再有从属于自己的附件。金明想买的东西很多，肯定会超过妈妈限定的 $1\sim k1∼k 表示，第 kk 等最重要。他还从因特网上查到了每件物品的价格。他希望在不超过 NN 元（可以等于 NN 元）的前提下，使每件物品的价格与重要度的乘积的总和最大。$

设第 $j_1,j_2,...,j_kj1,j2,...,jk ，则所求的总和为：$

$v[j_1]\times p[j_1]+v[j_2]\times p[j_2]+...+v[j_k]\times p[j_k]v[j1]×p[j1]+v[j2]×p[j2]+...+v[jk]×p[jk]$

现在

输入格式

第 $11行，为两个正整数，用一个空格隔开：N\;mNm（其中NN表示总钱数，mm为希望购买物品的个数。）$

从第 $v_{i-1}\;p_{i-1}\;q_{i-1}vi−1pi−1qi−1（其中v_{i-1}vi−1表示该物品的价格，p_{i-1}pi−1表示该物品的重要度，q_{i-1}qi−1表示该物品是主件还是附件。如果 q_{i-1}=0qi−1=0，表示该物品为主件，如果 q_{i-1}>0qi−1>0，表示该物品为附件，q_{i-1}qi−1是所属主件的编号）$

输出格式

一个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值。

输入输出样例

输入 #1复制

1000 5800 2 0400 5 1300 5 1400 3 0500 2 0

输出 #1复制

输入 #2复制

10000 20300 2 0500 2 1200 4 1800 1 1600 5 1650 3 1600 3 1750 2 1650 1 1850 4 1550 3 1850 2 1700 4 1950 1 1950 5 1700 5 1500 2 1650 3 1800 3 1850 4 1

输出 #2复制

说明/提示

数据范围：

样例解释：

1：选择

2：选择

提示：

请注意时间和空间限制。

可以使用

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;int n,m;int f[5000010],h[5000010];struct node{ int v,p,q;}a[1010];int read(){ int a=0,b=1; char ch=getchar(); while((ch<48||ch>57)&&ch!='-'){ ch=getchar(); } if(ch=='-'){ b=-1; ch=getchar(); } while(ch<48||ch>57){ ch=getchar(); } while(ch>47&&ch<58){ a=a*10+ch-48; ch=getchar(); } return a*b;}int main(){ n=read(),m=read(); for(int i=1;i<=m;i++){ a[i].v=read(),a[i].p=read(),a[i].q=read(); a[i].p*=a[i].v; } for(int i=1;i<=m;i++){ if(!a[i].q){ for(int j=1;j
            
             =a[i].v+a[j].v;k--){ h[k]=max(h[k],h[k-a[j].v]+a[j].p); } } } for(int j=a[i].v;j<=n;j++){ f[j]=max(f[j],h[j]); } } } printf("%d",f[n]); return 0;}

转载于:https://www.cnblogs.com/xiongchongwen/p/11388057.html

你可能感兴趣的文章