题解【BZOJ4145】「AMPPZ2014」The Prices
2024-10-08 09:42:20
题目描述
你要购买 \(m\) 种物品各一件,一共有 \(n\) 家商店,你到第 \(i\) 家商店的路费为 \(d[i]\),在第 \(i\) 家商店购买第 \(j\) 种物品的费用为 \(c[i][j],\)求最小总费用。
输入格式
第一行包含两个正整数\(n,m\)(\(1\leq n\leq 100,1\leq m\leq 16\)),表示商店数和物品数。
接下来 \(n\) 行,每行第一个正整数 \(d[i]\)(\(1\leq d[i]\leq 1000000\))表示到第 \(i\) 家商店的路费;接下来 \(m\) 个正整数,依次表示 \(c[i][j]\)(\(1\leq c[i][j]\leq 1000000\))。
输出格式
一个正整数,即最小总费用。
输入输出样例
输入 #1
3 4
5 7 3 7 9
2 1 20 3 2
8 1 20 1 1
输出 #1
16
说明/提示
样例解释
在第一家店买 2 号物品,在第二家店买剩下的物品。
题解
设\(dp[i][S]\)表示前\(i\)个商店,已买物品的集合为\(S\)的最小费用。
则有:\(dp[i][S | (1 << (j - 1))] = min(dp[i][S | (1 << (j - 1))], dp[i][S]+c[i][j])\)。
其中,\(j\)为当前要买的物品,\(S\)为枚举的子集,\(i\)为枚举的商店。
每次初始化\(dp[i][S]=dp[i-1][S]+d[i]\)。
每次做完\(DP\)后更新\(dp[i][S]=min(dp[i][S],dp[i-1][S])\),记录前缀最小值。
答案为\(dp[n][(1<< m)-1]\)。
代码
/********************************
Author: csxsl
Date: 2019/10/24
Language: C++
Problem: BZOJ4145
********************************/
#include <bits/stdc++.h>
#define itn int
#define gI gi
using namespace std;
inline int gi()
{
int f = 1, x = 0; char c = getchar();
while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}
while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return f * x;
}
inline long long gl()
{
long long f = 1, x = 0; char c = getchar();
while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}
while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return f * x;
}
const int maxn = 101, maxm = (1 << 16) + 1;
int n, m, d[maxn], c[maxn][17];
long long dp[maxn][maxm];
int main()
{
//freopen(".in", "r", stdin);
//freopen(".out", "w", stdout);
n = gi(), m = gi();
for (int i = 1; i <= n; i+=1)
{
d[i] = gi();
for (int j = 1; j <= m; j+=1) c[i][j] = gi();
}
//输入
memset(dp, 0x7f, sizeof(dp));
dp[0][0] = 0;//初始化
for (int i = 1; i <= n; i+=1)//枚举商店
{
for (int S = 0; S < (1 << m); S+=1) dp[i][S] = dp[i - 1][S] + d[i];//先初始化dp[i][S]
for (int j = 1; j <= m; j+=1)//枚举物品
for (int S = 0; S < (1 << m); S+=1)//枚举子集
if (!(S & (1 << (j - 1))))//如果还没有买j物品
dp[i][S | (1 << (j - 1))] = min(dp[i][S | (1 << (j - 1))], dp[i][S] + c[i][j]);//转移
for (int S = 0; S < (1 << m); S+=1) dp[i][S] = min(dp[i][S], dp[i - 1][S]);//更新
}
printf("%lld\n", dp[n][(1 << m) - 1]);//输出
return 0;
}
最新文章
- 【无私分享:ASP.NET CORE 项目实战(第四章)】Code First 创建数据库和数据表
- AC日记——过滤多余的空格 1.7 23
- 巧用jQuery选择器写表单办法总结(提高效率)
- create file遇到操作系统错误5拒绝访问
- 多个Storyboard的使用
- zoj 3599 Game 博弈论
- poj 1077 Eight(A*)
- delphi 获取北京时间(使用XMLHTTP获取百度的时间,WebBrowser获取www.timedate.cn的时间)
- python版本wifi共享工具
- 【BZOJ3282】Tree (Link-Cut Tree)
- capwap学习笔记——初识capwap(四)(转)
- Tomcat的测试网页换成自己项目首页
- 重谈react优势——react技术栈回顾
- 授权oAuth
- SpringCloud学习资料
- [Learn AF3]第七章 App framework组件之Popup
- SQL Server Management Studio (SSMS) 清除登录记录
- PHPCMS V9标签循环嵌套调用数据的方法
- phpredis用法笔记
- [BZOJ3638 &;&; BZOJ3272]带修区间不相交最大K子段和(线段树模拟费用流)
热门文章
- STL函数 lower_bound 和 upper_bound 在算法竞赛中的用法
- JZOJ5988 珂学计树题
- Wannafly Camp 2020 Day 3D 求和 - 莫比乌斯反演,整除分块,STL,杜教筛
- 小白的java学习之路 “ 字符串”
- springboot~gradle4.7之后的lombok引用方法
- k8s获取apiversion下面的对应可用资源
- knitr::kable实现结构化展示数据
- Hadoop的安装(2)---Hadoop配置
- ubuntu set up 4 - 设置和软件
- SIFT解析(一)高斯模糊