1025. 开餐馆
题意
信息学院的同学小明毕业之后打算创业开餐馆.现在共有 n 个地点可供选择。
小明打算从中选择合适的位置开设一些餐馆。
这 n个地点排列在同一条直线上。
我们用一个整数序列 m 1 , m 2 , … , m n 来表示他们的相对位置。
由于地段关系,开餐馆的利润会有所不同。我们用 p i 表示在 m i处开餐馆的利润。
为了避免自己的餐馆的内部竞争,餐馆之间的距离必须大于 k。
请你帮助小明选择一个总利润最大的方案。
思路
线性dp模板题
状态表示：f[i] 表示从前 i 个餐馆中选择如何开店的利润的最大值
状态转移：可以将状态划分成倒数第二个选择哪个餐馆 有两种状态
第一种：倒数第二个餐馆离当前的餐馆距离大于 k 那么可以共存
第二种：倒数第二个餐馆离当前的餐馆距离小于等于 k 要么选择当前的餐馆 要么舍弃当前的餐馆
代码
#include<bits/stdc++.h> #define INF 0x3f3f3f3f #define mod 998244353 #define endl '\n' using namespace std; typedef long long LL; typedef pair<int, int>PII; const int N = 600; int n, k; int m[N], p[N]; int f[N]; void solve() { cin >> n >> k; for (int i = 1; i <= n; ++i)scanf("%d", &m[i]); for (int i = 1; i <= n; ++i)scanf("%d", &p[i]); memset(f, 0, sizeof f); f[1] = p[1]; for (int i = 1; i <= n; ++i) { for (int j = 1; j <= i; ++j) { if (m[j] + k < m[i]) //如果可以选当前的餐馆 f[i] = max(f[i], f[j] + p[i]); else f[i] = max(f[i], f[j]); //不能选当前的餐馆情况下的选择一：选择之前的 //舍弃现在的 } f[i] = max(f[i], p[i]); //不能选当前餐馆的情况下的选择二：选择现在的 舍弃之前的 } cout << f[n] << endl; } int main() { int t; cin >> t; while(t--) solve(); return 0; }
