[离散化dp] NC19809 growth

题面

link    一开始有属性a和b，这两个属性初始的时候均为0，每一天可以让a涨1点或b涨1点。我们共有 $n$ 种奖励，第i种奖励有 $x_i，y_i，z_i$ 三种属性，若 $a\ge x_i$ 且 $b\ge y_i$，则弱弱在接下来的每一天都可以得到 $z_i$ 的分数。    问 $m$ 天以后弱弱最多能得到多少分数，其中 $1\le n\le 1000，1\le m\le 2e9,x_i,y_i\le 1e9$。   

分析

  当 $m$ 很小时，可以想到动态规划的方法。若 $dp[i][j]$ 表示 $i+j$ 天且 $a=i,b=j$ 时得到的最大奖励，那么这个值肯定和之前状态有关， 若用 $v[i][j]$ 表示 $a=i,b=j$ 时这一天可以得到的奖励，那么可以得到这样的状态转移方程： $$dp[i][j]=max(dp[i-1][j],dp[i][j-1])+v[i][j]$$    而对于$v[i][j]$, 我们可以用前缀和的方法进行求解，若是初始时 $v[i][j]$ 表示 $x=i,b=j$ 的属性的 $z$ 值，可以得到这样的状态转移方程： $$v[i][j]+=v[i-1][j]+v[i][j-1]-v[i-1][j-1]$$   这个可以类比一维的求前缀和得到，也可以简单地类比面积计算得到：   若 $S$ 初始表示右上那一块小的，若要表示大长方形面积，对应 $v[i][j]$, $S_1$ 对应左边两块，对应 $v[i-1][j]$, $S_2$ 对应下边两块，对应 $v[i][j-1]$, $S_3$ 对应左下那块，对应 $v[i-1][j-1]$, 则 $S+=S_1+S_2-S_3$，对应于上述求前缀和转移式。   而对于ans: $$ans=max(ans,dp[i][j]+v[i][j]\ast (m-i-j))(i+j\ge m)$$   而这一题 $m$ 的范围是很大的，通过直接枚举天数进行dp肯定会超时。所以这时候可以想到离散化。

  比如当有3个奖励: $(100,100,1),(20,30,2),(30,20,3)$，对于 $dp[100][100]$, 只需要考虑 $dp[20][30],dp[30][20],dp[30,30]$ 这些值怎么变化到 $dp[100][100]$ 就好了，而无需从 $dp[100][99],dp[99][100]$ 这些值得到，因此我们只需要考虑这些奖励的 $x_i,y_i$ 所组成的结点就好了。为此我们需要将 $x_i,y_i$ 离散化：

scanf("%d %d", &n, &m); for(int i = 1; i <= n; i++) { scanf("%d %d %d", &pro[i].x, &pro[i].y, &pro[i].z); X[i] = pro[i].x; Y[i] = pro[i].y; } //先排序 sort(X + 1, X + 1 + n); //先排序 sort(Y + 1, Y + 1 + n); //再去重，得到去重后的元素个数 cnt1 = unique(X + 1, X + 1 + n) - (X + 1); cnt2 = unique(Y + 1, Y + 1 + n) - (Y + 1); for(int i = 1; i <= n; i++) { //将值从小到大排序后，依次映射到1， 2.... int x = lower_bound(X + 1, X + 1 + cnt1, pro[i].x) - X, y = lower_bound(Y + 1, Y + 1 + cnt2, pro[i].y) - Y; v[x][y] += pro[i].z; }

  其中 $X[i]$ 中的值分别映射到 $1,2...$   经过这样的映射之后，我们只对奖励里出现过的值进行遍历，比如上面的例子从 $1$ 遍历到 $100$ 可以变成 $1$ 遍历到 $3$ (其中 $1$ 对应 $20$， $2$ 对应 $30$， $3$ 对应 $100$)，那么原来 $dp[i][j]$ 与 $dp[i-1][j]$ 相差了 $1$ 天， 现在就相差 $X[i]-X[i-1]$ 天。   求 $v[i][j]$ 的转移方程没有变，而求 $dp[i][j]$ 的转移方程为： $$dp[i][j]=max(dp[i-1][j]+v[i-1][j]\ast (X[i]-X[i-1]-1),dp[i][j-1]+v[i][j-1]\ast (Y[j]-Y[j-1]-1))+v[i][j]$$   对于每一个 $dp[i][j]$，若 $i+j\le m$， 那么： $$ans=max(ans,dp[i][j]+(m-X[i]-Y[j])\ast v[i][j])$$

  这样得到的即为需要的最大值，其中离散化操作为 $O(nlogn)$, 求前缀和，dp 为 $O(n^2)$

  

代码

#include <bits/stdc++.h> using namespace std; typedef unsigned long long ll; const int maxn = 1005; const int INF = 0x3f3f3f3f; const ll mod = 998244353; struct node { int x, y, z; }pro[maxn]; int n, m, X[maxn], Y[maxn], cnt1, cnt2; ll dp[maxn][maxn], v[maxn][maxn], ans; int main() { scanf("%d %d", &n, &m); //进行离散化操作 for(int i = 1; i <= n; i++) { scanf("%d %d %d", &pro[i].x, &pro[i].y, &pro[i].z); X[i] = pro[i].x; Y[i] = pro[i].y; } sort(X + 1, X + 1 + n); //排序 sort(Y + 1, Y + 1 + n); cnt1 = unique(X + 1, X + 1 + n) - (X + 1); //去重 cnt2 = unique(Y + 1, Y + 1 + n) - (Y + 1); for(int i = 1; i <= n; i++) { ///将值从小到大排序后，依次映射到1， 2.... int x = lower_bound(X + 1, X + 1 + cnt1, pro[i].x) - X, y = lower_bound(Y + 1, Y + 1 + cnt2, pro[i].y) - Y; v[x][y] += pro[i].z; } for(int i = 1; i <= cnt1; i++) //求前缀和 for(int j = 1; j <= cnt2; j++) v[i][j] += v[i-1][j] + v[i][j-1] - v[i-1][j-1]; for(int i = 1; i <= cnt1; i++) { for(int j = 1; j <= cnt2; j++) //进行dp { dp[i][j] = max(dp[i-1][j] + v[i-1][j] * (X[i] - X[i-1] - 1), dp[i][j-1] + v[i][j-1] * (Y[j] - Y[j-1] - 1)) + v[i][j]; if(X[i] + Y[j] <= m) //这个if判断很关键！ ans = max(ans, dp[i][j] + (m - X[i] - Y[j]) * v[i][j]); } } printf("%lld\n", ans); }

  

一点收获

1.离散化的三步骤：①排序； ②去重； ③二分查找用下标对应值 2.二维求前缀和的方法