上海计算机学会2022年11月月赛C++乙组T3菜单设计
发布时间
阅读量：
阅读量
菜单设计
内存限制: 256 Mb 时间限制: 1000 ms
题目描述
小爱需要从 n 道菜中，选出 m 道菜作为餐厅的菜单。已知第 i 道菜的美味值为 xi。还有 p 种加分规则，第 i 条规则包含三个参数 ai 、bi 和 ci，表示在第 ai 道菜后，如果下一道菜是 bi 道，会有额外 ci 点美味值。
如何设计菜单，才能使美味值到达最大。
输入格式
输入第一行，两个正整数n,m
输入第二行，𝑛n个正整数，x1,...,xn
输入第三行，一个正整数，p
接下来p行，每行3个正整数，分别表示第i条建议的三个参数ai,bi,ci
输出格式
输出一个正整数，表示所选菜单能获得的最大美味值。
数据范围
- 对于 50% 数据，1≤m≤n≤8；
- 对于 100% 数据，1≤m≤n≤18；
0≤xi,ci≤10^9,1≤ai,bi≤n ，1≤p≤n×(n−1) 。
数据保证没有两条菜品建议的ai和bi完全相同
样例数据
输入:
4 3
2 5 1 3
2
2 1 6
4 3 1
输出:
16
说明:
按第2道、第1道、第4道备选菜肴的顺序组成正式菜单
获得 2+5+3=10 点美味值，外加第2道后接第1道备选菜肴所带来的 6 点额外美味值
故最大美味值为 16
解析：状态压缩DP（动态规划）
详见代码：
#include <bits/stdc++.h>
using namespace std;
const long long maxn = 20;
long long dp[(1 << maxn)][maxn];
long long v[maxn];
long long pp[maxn][maxn];
long long n, m, k;
long long max(long long x, long long y) {
if(x < y)return y;
return x;
}
long long _count(long long x) {
long long an = 0;
while(x) {
if(x & 1)an++;
x >>= 1;
}
return an;
}
int main() {
scanf("%lld%lld", &n, &m);
for(int i = 0; i <= n - 1; i++) {
scanf("%lld", &v[i]);
}
scanf("%lld", &k);
for(int i = 1; i <= k; i++) {
int x, y;
long long z;
cin >> x >> y >> z;
pp[x - 1][y - 1] = z;
}
long long ans = 0;
for(int i = 0; i <= n - 1; i++)
dp[(1 << i)][i] = v[i];
for(int i = 1; i < (1 << n); i++) {
int qw = _count(i);
if(qw > m)continue;
if(qw == m) {
for(int j = 0; j <= n - 1; j++)
ans = max(ans, dp[i][j]);
continue;
} else {
for(int j = 0; j <= n - 1; j++) { //枚举没有吃的
if(((1 << j)&i) == 0) { //没有吃
for(int k = 0; k <= n - 1; k++) //枚举最后吃的点
if(((1 << k)&i)) //吃过
dp[i | (1 << j)][j] = max(dp[i][k] + pp[k][j] + v[j], dp[i | (1 << j)][j]);
}
}
}
}
printf("%lld", ans);
return 0;
}
AI写代码cpp
全部评论 (0)
还没有任何评论哟~