2021ICPC昆明 G.Gift

题目链接

题目描述
EQWE is a pastry chef who has $N$ friends. This year (obviously, the year $2021$), he wants to give each friend a birthday cake made by himself.

If EQWE wants to give the $i$-th friend a birthday cake made by himself, he need c i c_i ci​ days (do NOT need to be contiguous) before his friend’s birthday to make it. After that he will get v i v_i vi​ favorable impression. Note that it will be OK for him to finish the cake exactly on the birthday, as birthday parties are always held at night.

But EQWE doesn’t have much time and he has another plan. There are $M$ special gifts in the shop. EQWE can pay a j a_j aj​ yuan to get the $j$-th special gift and send it to any friend. Note that each gift is unique, which means that he can buy each gift at most once. After that he will get b j b_j bj​ favorable impression.

EQWE’s friends are very polite, so they do NOT want to receive more than one gift (including birthday cakes and special gifts). Note that to gain some favorable impression from a friend, the selected gift must be sent on the exact date of the friend’s birthday.

Suppose that it is the first day of the year $2021$ now (and he can start making birthday cakes immediately), and EQWE has $W$ yuan. What’s the maximum number of favorable impression that EQWE can get in $2021$?
输入描述:
The input file starts with an integer $T(1\le T\le 100)$, denoting the number of test cases. Then $T$ test cases follow.

For each test case, the first line contains three integers N ( 1 ≤ N ≤ 500 ) , M ( 1 ≤ M ≤ 15 ) , W ( 1 ≤ W ≤ 1 0 4 ) N(1\le N\le 500),M(1\le M\le 15),W(1\le W\le 10^4) N(1≤N≤500),M(1≤M≤15),W(1≤W≤104) , denoting the number of friends, the number of special gifts, and the amount of money that EQWE has.

Each of the following $N$ lines describes a friend, in the format of y e a r − m o n t h − d a y c i v i year-month-day\ c_i\ v_i year−month−day ci​ vi​ , where $year-month-day$ is the date of the friend’s birthday, c i ( 1 ≤ c i ≤ 30 ) c_i(1\leq c_i\leq 30) ci​(1≤ci​≤30) is the day needed to make the birthday cake for the friend, and v i ( 1 ≤ v i ≤ 1 0 6 ) v_i(1\leq v_i\leq 10^6) vi​(1≤vi​≤106) is the favorable impression that EQWE can get. It is guaranteed that c i , v i c_i,v_i ci​,vi​ are integers. It is also guaranteed that the date given are all valid dates between the year $1990$ and $2010$, that is, $year$ is an integer between $1990$ and $2010$, $month$ is an integer between $1$ and $12$, and $day$ is a positive integer which do not exceed the number of days in the given month.

The next $M$ lines describe the special gifts, the $i$-th of which contain two inte The i t h i^{th} ith line is a i b i ( 1 ≤ a i ≤ W , 1 ≤ b i ≤ 1 0 6 ) a_i\ b_i(1\le a_i \le W,1\le b_i\le 10^6) ai​ bi​(1≤ai​≤W,1≤bi​≤106)
输出描述:
For each test case, output a line containing a single integer, denoting the maximum number of favorable impression that EQWE can get.
示例1
输入

1
2 2 100
2000-01-01 10 13
2000-12-31 30 92
99 46
2 2

输出

138

数据水，读错题都能AC
首先需要求出送 $i$ 个礼物在花费不超过 $W$ 的情况下的最大收益 $mx[i]$ 。
设 $dp[i][k][j]$ 表示前 $i$ 个礼物中选择 $k$ 个且花费为 $j$ 时的最大收益，则有转移方程如下：
$$dp[i][k][j]=\max (dp[i-1][k][j],dp[i-1][k-1][j-a[i]]+b[i])$$
其中：
m x [ i ] = max ⁡ j = 1 W d p [ M ] [ i ] [ j ] mx[i]=\max_{j=1}^Wdp[M][i][j] mx[i]=j=1maxW​dp[M][i][j]
这样可以在 O ( M 2 W ) O(M^2W) O(M2W) 的时间复杂度下预处理 $mx[i]$ 。
其实，由于 $M$ 最多只有 $15$ ，暴力枚举也可以在 O ( M 2 M ) O(M2^M) O(M2M) 的时间复杂度下预处理出 $mx[i]$（比 $dp$ 还要快一些）。
先将每个人信息按生日先后顺序排序。
如果设 $dp[i][k][j]$ 表示对于前 $i$ 个人有不超过 $j$ 天空闲，有 $k$ 个人没有被送蛋糕的情况下送蛋糕的最大收益，则该dp的时间复杂度为 O ( 365 N 2 ) O(365N^2) O(365N2) ，由于有多组测试数据，该算法复杂度过大，无法通过该题。因此考虑将一些状态合并来降低复杂度。
设 $dp[i][k][j]$ 表示对于前 $i$ 个人有不超过 $j$ 天空闲，有 $x$ $(\min (x,M)=k)$ 个人没有被送蛋糕的情况下送蛋糕的最大收益。则转移方程如下：
{ d p [ i ] [ k ] [ j + t [ i ] − t [ i − 1 ] − c [ i ] ] = max ⁡ ( d p [ i ] [ k ] [ j + t [ i ] − t [ i − 1 ] − c [ i ] ] , d p [ i − 1 ] [ k ] [ j ] + v [ i ] ) d p [ i ] [ k ] [ j + t [ i ] − t [ i − 1 ] ] = max ⁡ ( d p [ i ] [ k ] [ j + t [ i ] − t [ i − 1 ] ] , d p [ i − 1 ] [ k − 1 ] [ j ] ) d p [ i ] [ M ] [ j + t [ i ] − t [ i − 1 ] ] = max ⁡ ( d p [ i ] [ M ] [ j + t [ i ] − t [ i − 1 ] ] , d p [ i − 1 ] [ M ] [ j ] ) d p [ i ] [ k ] [ j ] = max ⁡ ( d p [ i ] [ k ] [ j ] , d p [ i ] [ k ] [ j + 1 ] ) \left\{\begin{matrix} dp[i][k][j+t[i]-t[i-1]-c[i]]=\max(dp[i][k][j+t[i]-t[i-1]-c[i]],dp[i-1][k][j]+v[i])\\ dp[i][k][j+t[i]-t[i-1]]=\max(dp[i][k][j+t[i]-t[i-1]],dp[i-1][k-1][j])\\ dp[i][M][j+t[i]-t[i-1]]=\max(dp[i][M][j+t[i]-t[i-1]],dp[i-1][M][j])\\ dp[i][k][j]=\max(dp[i][k][j],dp[i][k][j+1]) \end{matrix}\right. ⎩⎪⎪⎨⎪⎪⎧​dp[i][k][j+t[i]−t[i−1]−c[i]]=max(dp[i][k][j+t[i]−t[i−1]−c[i]],dp[i−1][k][j]+v[i])dp[i][k][j+t[i]−t[i−1]]=max(dp[i][k][j+t[i]−t[i−1]],dp[i−1][k−1][j])dp[i][M][j+t[i]−t[i−1]]=max(dp[i][M][j+t[i]−t[i−1]],dp[i−1][M][j])dp[i][k][j]=max(dp[i][k][j],dp[i][k][j+1])​
初始状态 $dp[0][0][0]=0,dp[0][1][0]=-\inf$ 。
其中第一个转移方程表示给第 $i$ 个人送蛋糕；第二、三个转移方程表示不给第 $i$ 个人送蛋糕；第四个转移方程用来维护前面“不超过”的定义。最终答案为 max ⁡ i = 0 M ( d p [ N ] [ i ] [ 0 ] + m x [ i ] ) \max\limits_{i=0}^M(dp[N][i][0]+mx[i]) i=0maxM​(dp[N][i][0]+mx[i]) 。
该dp的时间复杂度为 $O(365NM)$ 。因此总时间复杂度为 O ( T ( M 2 M + 365 N M ) ) O(T(M2^M+365NM)) O(T(M2M+365NM)) 。

#include#define lowbit(x) (x&(-(x)))
using namespace std;
const int sum[13] = {0, 0, 31, 59, 90, 120, 151, 181, 212, 243, 273, 304, 334};struct node {int c, v, t;inline bool operator<(node a) const {return t < a.t;}
};int T, n, m, w, tot;
int a[15], b[15], dp[2][16][366], mx[16];
node p[505];
char t[11];int main() {scanf("%d", &T);while (T--) {scanf("%d%d%d", &n, &m, &w);tot = 0;for (int i = 1; i <= n; i++) {++tot, scanf("%s%d%d", t, &p[tot].c, &p[tot].v);if (t[5] == '0' && t[6] == '2' && t[8] == '2' && t[9] == '9') {tot--;continue;}p[tot].t = sum[(t[5] - '0') * 10 + (t[6] - '0')] + (t[8] - '0') * 10 + t[9] - '0';}sort(p + 1, p + 1 + tot);for (int i = 0; i < m; i++)scanf("%d%d", &a[i], &b[i]);memset(mx, 0, sizeof(int) * (m + 1));for (int s = 1; s < (1 << m); s++) {int sa = 0, sb = 0, i = 0;for (int x = s, j; x && sa <= w; x -= lowbit(x), i++)j = __builtin_ctz(x), sa += a[j], sb += b[j];if (sa <= w)mx[i] = max(mx[i], sb);}for (int i = 1; i <= m; i++)mx[i] = max(mx[i], mx[i - 1]);int ans = 0;dp[0][0][0] = 0, dp[0][1][0] = -0x3f3f3f3f;for (int i = 1; i <= tot; i++) {for (int j = 0; j <= min(i + 1, m); j++)memset(dp[i & 1][j], -0x3f, sizeof(int) * (p[i].t + 1));for (int j = 0, d; j <= p[i - 1].t; j++) {d = j + p[i].t - p[i - 1].t;for (int k = 0; k <= min(m, i); k++) {if (d - p[i].c >= 0)dp[i & 1][k][d - p[i].c] = max(dp[i & 1][k][d - p[i].c], dp[i - 1 & 1][k][j] + p[i].v);if (k)dp[i & 1][k][d] = max(dp[i & 1][k][d], dp[i - 1 & 1][k - 1][j]);}if (i > m)dp[i & 1][m][d] = max(dp[i & 1][m][d], dp[i - 1 & 1][m][j]);}for (int j = p[i].t - 1; j >= 0; j--)for (int k = 0; k <= min(m, i); k++)dp[i & 1][k][j] = max(dp[i & 1][k][j], dp[i & 1][k][j + 1]);}for (int i = 0; i <= m; i++)ans = max(ans, dp[tot & 1][i][0] + mx[i]);printf("%d\n", ans);}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！