洛谷1070 道路游戏

原题链接

太菜了，只会(O(n^3))暴力(DP)，最后看大佬的博客看了好久也是一知半解。。
大佬博客传送门

#include<cstdio>
#include<cstring>
using namespace std;
const int N = 1010;
struct dd{
	int l, r, v[N], id[N];
};
dd q[N];
int f[N], mo[N][N], S[N][N], co[N], n;
inline int re()
{
	int x = 0;
	char c = getchar();
	bool p = 0;
	for (; c < '0' || c > '9'; c = getchar())
		p |= c == '-';
	for (; c >= '0' && c <= '9'; c = getchar())
		x = x * 10 + c - '0';
	return p ? -x : x;
}
inline int maxn(int x, int y)
{
	return x > y ? x : y;
}
inline int pos(int x, int y)
{
	return ((x - y) % n + n) % n;
}
int main()
{
	int i, j, k, m, p, o;
	n = re();
	m = re();
	p = re();
	for (i = 0; i < n; i++)
		for (j = 1; j <= m; j++)
			S[i][j] = re();
	for (i = 0; i < n; i++)
	{
		co[i] = re();
		j = (i + 1) ^ n ? i + 1 : 0;
		q[j].l = 1;
		q[j].v[++q[j].r] = -co[i];
	}
	for (j = 2; j <= m; j++)
		for (i = 0; i < n; i++)
			S[i][j] += S[(i + n - 1) % n][j - 1];
	memset(f, 250, sizeof(f));
	f[0] = 0;
	for (i = 1; i <= m; i++)
	{
		for (j = 0; j < n; j++)
		{
			k = pos(j, i - 1);
			f[i] = maxn(f[i], q[k].v[q[k].l] + S[pos(j, 1)][i]);
		}
		for (j = 0; j < n; j++)
		{
			k = pos(j, i - 1);
			for (; q[k].l <= q[k].r && q[k].id[q[k].l] < i - p + 1; q[k].l++);
			o = f[i] - S[pos(j, 1)][i] - co[j];
			for (; q[k].l <= q[k].r && q[k].v[q[k].r] < o; q[k].r--);
			q[k].v[++q[k].r] = o;
			q[k].id[q[k].r] = i;
		}
	}
	printf("%d", f[m]);
	return 0;
}