ACM模版

## 题解

dp[i][j]dp[i][j] 表示从最北边到第 ii 行第 jj 列的最大高兴值，很容易想就是枚举前一行状态进行转移，但是会超时，所以我们只需要利用单调队列来维护一下即可，具体的思路请参考 林燕同学的博客，这都是套路……愿区域赛少一些套路，多一些真诚~~~

## 代码

```#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <deque>

using namespace std;

const int MAXN = 111;
const int MAXM = 1e4 + 10;

int n, m, k;
int sum[MAXM];
int dp[MAXN][MAXM];
int wel[MAXN][MAXM];
int len[MAXN][MAXM];

template <class T>
inline bool scan_d(T &ret)
{
char c;
int sgn;
if (c = getchar(), c == EOF)
{
return 0;   //  EOF
}
while (c != '-' && (c < '0' || c > '9'))
{
c = getchar();
}
sgn = (c == '-') ? -1 : 1;
ret = (c == '-') ? 0 : (c - '0');
while (c = getchar(), c >= '0' && c <= '9')
{
ret = ret * 10 + (c - '0');
}
ret *= sgn;
return 1;
}

struct node
{
int hap, dis;

node() {}
node(int h, int d) : hap(h), dis(d) {}
};

int main()
{
while (~scanf("%d%d%d", &n, &m, &k) && n + m + k)
{
++n;
memset(dp, 0, sizeof(dp));
memset(len, 0, sizeof(len));
memset(wel, 0, sizeof(wel));

for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
scan_d(wel[i][j]);
}
}

for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
scan_d(len[i][j]);
}
}

for (int i = 1; i <= n; i++)
{
deque<node> deq;
int dis = 0;
for (int j = 1; j <= m; j++)
{
sum[j] = sum[j - 1] + wel[i][j];
}

for (int j = 0; j <= m; j++)
{
dis += len[i][j];
while (!deq.empty() && deq.front().hap <= dp[i - 1][j] - sum[j])
{
deq.pop_front();
}
deq.push_front(node(dp[i - 1][j] - sum[j], dis));
while (!deq.empty() && deq.front().dis - deq.back().dis > k)
{
deq.pop_back();
}
dp[i][j] = deq.back().hap + sum[j];
}

deq.clear();
dis = 0;
len[i][m + 1] = 0;
for (int j = m; j >= 0; j--)
{
dis += len[i][j + 1];
while (!deq.empty() && deq.front().hap <= dp[i - 1][j] + sum[j])
{
deq.pop_front();
}
deq.push_front(node(dp[i - 1][j] + sum[j], dis));
while (!deq.empty() && deq.front().dis - deq.back().dis > k)
{
deq.pop_back();
}
dp[i][j] = max(dp[i][j], deq.back().hap - sum[j]);
}
}

int ans = 0;
for (int j = 0; j <= m; j++)
{
ans = max(ans, dp[n][j]);
}
printf("%d\n", ans);
}

return 0;
}```

101 篇文章37 人订阅

0 条评论

## 相关文章

60670

23740

1.3K60

38220

28900

29340

### Linux OOM机制分析

oom_killer（out of memory killer）是Linux内核的一种内存管理机制，在系统可用内存较少的情况下，内核为保证系统还能够继续运行下去...

1.4K70

15530

### catalan---卡特兰数（小结）

(关于卡特兰数的详细介绍)http://baike.baidu.com/view/2499752.htm 下面有练习的题目: 经过测试，_int64/long...

41970

### Oracle RAC OCR 的备份与恢复

Oracle Clusterware把整个集群的配置信息放在共享存储上，这些信息包括了集群节点的列表、集群数据库实例到节点的映射以及CRS应用...

13320