首页 > 代码库 > POJ 3926 Parade 单调队列优化DP

POJ 3926 Parade 单调队列优化DP

2024-07-15 00:13:56   223人阅读

来源：http://poj.org/problem?id=3926

题意：行n <= 100, 列m <= 10000，类似于数字三角形，一个人要从底下往上走，每层中可以左右走，但选定方向不能回头（向左不能再向右），每经过一段获得该段的一个值，并走了该段的距离，在同一层走的距离不能超过k。问走到最顶头，获得的总值最大是多少。

分析：dp[i][j]表示走到第i行第j列，获得的值最大为多少。则dp[i][j] = max(dp[i+1][p] + sum(p to j))，sum(p to j)表示第i行从第p列到第j列的值的和，同时p需要满足abs(p-j) <= k。前缀和处理sum，枚举i，j，p，这样是o(nm^2)的复杂度，超时。

如果我们只考虑从左往右走，那么就是类似求有长度上限的最大子段和的模型了。sum(k)表示第i行前k列的前缀和，改写转移方程 dp[i][j] = max(dp[i+1][p] + sum(j) - sum(p)) = max(dp[i+1][p] - sum(p)) + sum(j)，这下很清楚了，前一项就可以用单调队列来维护，使得状态转移的复杂度降到均摊o(1)。然后从右往左走再做一遍就可以了。

 1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5  6 int n, m, k; 7 int a[120][10100], b[120][10100], dp[120][10100]; 8 struct que{ 9     int v, d;10 } q[10100];11 inline int in(){12     char ch = getchar();13     while((ch < ‘0‘ || ch > ‘9‘) && ch != ‘-‘) ch = getchar();14     bool flag = false;15     if (ch == ‘-‘){16         flag = true;17         ch = getchar();18     }19     int ans = 0;20     while(ch >= ‘0‘ && ch <= ‘9‘){21         ans = ans*10 + ch-‘0‘;22         ch = getchar();23     }24     if (flag) return -ans;25     return ans;26 }27 int main()28 {29     while(scanf("%d%d%d", &n, &m, &k) && (n+m+k))30     {31         for (int i = 0; i <= n; i++)32             for (int j = 0; j < m; j++)33                 a[i][j] = in();34         for (int i = 0; i <= n; i++)35             for (int j = 0; j < m; j++)36                 b[i][j] = in();37         for (int j = 0; j <= m; j++)38             dp[n+1][j] = 0;39         for (int i = n; i >= 0; i--){40             int sum, head, tail, dis;41             sum = head = tail = dis = 0;42             dp[i][0] = dp[i+1][0];43             q[tail].v = dp[i][0];44             q[tail++].d = 0;45             for (int j = 1; j <= m; j++){46                 sum += a[i][j-1];47                 dis += b[i][j-1];48                 while(head < tail && dis - q[head].d > k) head ++;49                 while(head < tail && q[tail-1].v <= dp[i+1][j] - sum) tail --;50                 q[tail].d = dis;51                 q[tail++].v = dp[i+1][j] - sum;52                 dp[i][j] = q[head].v + sum;53             }54             sum = head = tail = dis = 0;55             q[tail].v = dp[i+1][m];56             q[tail++].d = 0;57             for (int j = m-1; j >= 0; j--){58                 sum += a[i][j];59                 dis += b[i][j];60                 while(head < tail && dis - q[head].d > k) head ++;61                 while(head < tail && q[tail-1].v <= dp[i+1][j] - sum) tail --;62                 q[tail].d = dis;63                 q[tail++].v = dp[i+1][j] - sum;64                 if (q[head].v + sum > dp[i][j]) dp[i][j] = q[head].v + sum;65             }66         }67         int ans = 0;68         for (int i = 0; i <= m; i++)69             if (dp[0][i] > ans) ans = dp[0][i];70         printf("%d\n", ans);71     }72     return 0;73 }

 


联系
我们