HihoCoder 1270 建造基地（完全背包）_1270 : 建造基地-程序员宅基地

题意:

$中文题目不再赘述$

分析:

$由于金属可以多用, 完全背包的模型啦$
$不过需要注意的是, 由于可以溢出, 所以把这部分的答案特判下$
$然后搞就行了$

代码:

//
//  Created by TaoSama on 2016-03-06
//  Copyright (c) 2016 TaoSama. All rights reserved.
//
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <set>
#include <vector>

using namespace std;
#define pr(x) cout << #x << " = " << x << "  "
#define prln(x) cout << #x << " = " << x << endl
const int N = 1e5 + 10, INF = 0x3f3f3f3f, MOD = 1e9 + 7;

int n, m, k, t, q;
int a[105], b[105];
typedef long long LL;

LL f[10005];
const LL INFLL = 0x3f3f3f3f3f3f3f3fLL;

int main() {
#ifdef LOCAL
    freopen("C:\\Users\\TaoSama\\Desktop\\in.txt", "r", stdin);
//  freopen("C:\\Users\\TaoSama\\Desktop\\out.txt","w",stdout);
#endif
    ios_base::sync_with_stdio(0);

    scanf("%d", &q);
    while(q--) {
        scanf("%d%d%d%d", &n, &m, &k, &t);
        for(int i = 1; i <= m; ++i) scanf("%d", a + i);
        for(int i = 1; i <= m; ++i) scanf("%d", b + i);
        LL ans = 0;
        bool can = true;
        while(n--) {
            memset(f, 0x3f, sizeof f);
            f[0] = 0;
            LL cur = INFLL;
            for(int i = 1; i <= m; ++i)
                for(int j = 0; j <= k; ++j)
                    if(j + b[i] > k) cur = min(cur, f[j] + a[i]);
                    else f[j + b[i]] = min(f[j + b[i]], f[j] + a[i]);
            cur = min(cur, f[k]);
            if(cur == INFLL) {can = false; break;}
            ans += cur;
            for(int i = 1; i <= m; ++i) b[i] /= t;
        }
        if(can) printf("%lld\n", ans);
        else puts("No Answer");
    }
    return 0;
}

本文链接：https://blog.csdn.net/lwt36/article/details/50820580

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

云计算需要学习什么开发语言-程序员宅基地

文章浏览阅读2.2k次。云计算开发需要掌握多种编程语言，具体取决于您要开发的云计算应用的类型和平台。一些常见的云计算开发语言包括: Python: 广泛用于云计算开发，因其简单易学的特点以及丰富的第三方库。Java: 广泛用于大型企业级应用，因其稳定性和可靠性。Go: 被广泛用于构建分布式系统，因其高效和简单易用的特点。Ruby: 广泛用于构建快速原型和小型云计算应用，因其简单易学和动态语言的特点。..._云计算用什么语言开发

统一认证 ldap mysql_ZABBIX 对接 LDAP实现用户登陆统一认证-程序员宅基地

文章浏览阅读352次。ZABBIX 认证方式有三种，分别是Internal、LDAP和HTTP。注意：实现LDAP用户账户统一认证需要AD和ZABBIX共有用户帐号并且保证LDAP设置中 Test authentication 选项中用户和密码和AD中的相同。Windows AD域创建OU zabbix 在OU中创建账号设置账号密码 OU中用户账户 ZABBIX Server查看php 是否安装ldap 模块 LDA..._zabbix mysql ldap設定

input file图片上传并回显_input file回显-程序员宅基地

文章浏览阅读7.8k次。// 图片上传借助于html5的文件读取实现<input type="file"multiple id="inputs"/>//multiple(多文件上传)_input file回显

不兼容android5.1.1,Android5.1.1启动问题-程序员宅基地

文章浏览阅读903次。本帖最后由 xujin071 于 2016-12-12 11:27 编辑新买回的firefly-rk3288开发板，烧入最新的Android5.1.1编译的固件，一直卡在Android字符界面，进不了桌面，各位版主帮忙分析一下启动log信息。[ 2.338220] ======== PULL WL_REG_ON LOW! ========[ 2.338228] [WLAN_RFKILL..._tk_btusb( 0): btchr_open: device not probed

python截图黑屏_对Python获取屏幕截图的4种方法详解-程序员宅基地

文章浏览阅读2.6k次，点赞2次，收藏2次。Python获取电脑截图有多种方式，具体如下：PIL中的ImageGrab模块windows APIPyQtpyautoguiPIL中的ImageGrab模块import timeimport numpy as npfrom PIL import ImageGrabimg = ImageGrab.grab(bbox=(100, 161, 1141, 610))img = np.array(img...._win32gui截屏黑屏

易语言代码转换python_易语言通过文本解析的方式把C代码转换成易代码-程序员宅基地

文章浏览阅读1.1k次。常量数据表.版本 2.常量 c, "", , '常量值是一段C代码C代码转易代码.版本 2.支持库 commobj.支持库 iext2.程序集窗口程序集_启动窗口.程序集变量 k, 快速文本对象.程序集变量 k2, 快速文本对象.子程序 __启动窗口_创建完毕.局部变量 z, 字符格式z.字体大小＝ 8z.字体名称＝ “微软雅黑”d1.置默认字符格式 (z)d2.置默认字符格式 (z)d1...._易语言转python