问题 A: building-布布扣-bubuko.com

题目描述

WOW是BLIZZARD公司开发的一款网络游戏，游戏的背景是处在一个叫做艾泽拉斯的神秘大陆上的。在这片陆地上生活着许多不同种族不同部落的奇幻生物，暗夜精灵就是其中的一员。他们拥有高深的科技和强大的魔法，但却因为性格的冷傲孤僻而不被其他种族所接受。为了改善这种状况，半神塞纳留斯决定发展有暗夜精灵族特色的产业来吸引外族，他发现暗夜精灵的建筑风格深受世人青睐，因为它们都是古树的造型，且具有一种神奇的魔力，就是在占地面积不变的情况下可以自由改变形状，使得建筑之间完全没有空隙。
于是，他将这一艰巨的任务交给了部落中最具天赋的工程师守望者玛维，让他在一块面积为n（0<=n<=100）的土地上建造若干个建筑，这些建筑都有各自的占地面积q(0<=q<=100)，价格p(0<=w<=100)和魅力值v(0<=v<=100)。就暗夜精灵当前掌握的科技来看，他们可以建造m(0<=m<=100)种建筑，为了不使游客感到乏味，每一种建筑规定最多只能建一座。
你的任务就是替玛维想出一种选择建造的方案，使得最多用k(0<=k<=100)的金钱，在面积为n的土地上建出的建筑具有最高的魅力值。

输入

第一行有三个数m,n,k;以下有m行，分别包含了m种建筑的占地面积q，价格p和魅力值v。

输出

仅有一个数，为最高魅力值。

样例输入 Copy

样例输出 Copy

#include <iostream>

using namespace std;

const int N = 110;

int m, n, t;//m为种类，n为面积，k为钱数
int s[N], v[N], w[N];//s为占地面积，v所耗金钱，w为魅力值
int f[N][N][N];

int main(){
    cin >> m >> n >> t;
    
    for (int i = 1; i <= m; i ++ ) cin >> s[i] >> v[i] >> w[i];
    
    for (int i = 1; i <= m; i ++ )
        for (int j = 0; j <= n; j ++ )
            for (int k = 0; k <= t; k ++ ){
                f[i][j][k] = f[i - 1][j][k];
                if (j - s[i] >= 0 && k - v[i] >= 0) 
                    f[i][j][k] = max(f[i][j][k], f[i - 1][j - s[i]][k - v[i]] + w[i]);
            }
            
    cout << f[m][n][t] << endl;
    
    return 0;
}

问题 A: building

原文：https://www.cnblogs.com/Iamcookieandyou/p/13418694.html