ACM模版
描述
题解
这个题是需要用单调队列优化优化的动态规划问题，好多 OJOJ 上都有，其中 POJPOJ 数据比较强，需要用输入外挂，并且开 G G 才能过。
dp[i][j]dp[i][j] 表示从最北边到第 ii 行第 jj 列的最大高兴值，很容易想就是枚举前一行状态进行转移，但是会超时，所以我们只需要利用单调队列来维护一下即可，具体的思路请参考 林燕同学的博客，这都是套路……愿区域赛少一些套路，多一些真诚~~~
代码
代码语言：javascript复制#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("%dn", ans);
}
return 0;
}
